是I题的数据太水吗?网络流也能过?

对于(u,v),
建立(u,v'),(v', u)容量都是1
(S,u)容量是d[u]
(u',T)容量是d[u]
跑网络流。过了。
#include <bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;

const int maxn = 105;
const int maxm = 205;

struct Edge {
	int from, to, cap, flow, next;

	Edge(int x=0, int y=0, int c=0, int nex=0)
		: from(x), to(y), cap(c), next(nex) {
			flow = 0;
		}

}edges[100000];

int d[maxn], n, m, sum;
int first[maxn + maxm], cur[maxn + maxm], tots;
int S, T;

void addEdge(int x, int y, int c) {
	edges[tots] = Edge(x, y, c, first[x]);
	first[x] = tots++;
	edges[tots] = Edge(y, x, 0, first[y]);
	first[y] = tots++;
}

bool vis[maxn+maxm];
int dep[maxn+maxm];

bool BFS() {
	memset(vis, 0, sizeof(vis));
	queue<int> Q;
	Q.push(0);
	dep[0] = 0;
	vis[0] = 1;
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		for (int i = first[x]; i != -1; i = edges[i].next) {
			Edge &e = edges[i];
			if (!vis[e.to] && e.cap > e.flow) {
				vis[e.to] = 1;
				dep[e.to] = dep[x] + 1;
				Q.push(e.to);
			}
		}
	}
	return vis[T];
}

int DFS(int x, int a) {
	if (x == T || a == 0) return a;
	int flow = 0, f;
	for (int &i = cur[x]; i != -1; i = edges[i].next) {
		Edge &e = edges[i];
		if (dep[x]+1 == dep[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
			e.flow += f;
			edges[i^1].flow -= f;
			flow += f;
			a -= f;
			if (a == 0) break;
		}
	}
	return flow;
}

int main() {
	while (cin >> n >> m) {
		sum = 0;
		tots = 0;
		memset(first, -1, sizeof(first));
		for (int i = 1; i <= n; ++i) {
			cin >> d[i];
			sum += d[i];
		}
		S = 0;
		T = 2*n + 1;
		for (int i = 1; i <= n; ++i)
			addEdge(S, i, d[i]);
		for (int i = 0; i < m; ++i) {
			int x, y;
			cin >> x >> y;
			addEdge(x, y+n, 1);
			addEdge(y, x+n, 1);
		}
		for (int i = n+1; i <= 2*n; ++i)
			addEdge(i, T, d[i-n]);
		int flow = 0;
		while (BFS()) {
			for (int i = S; i <= T; ++i)
				cur[i] = first[i];
			flow += DFS(S, INF);
		}
		if (flow == sum) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}


全部评论
拆点后都不能保证正反边一样,比如1匹配了2,2匹配了3,3匹配了4,4匹配了1.1->2,2->3,3->4,4->1
1 回复 分享
发布于 2020-07-12 23:21
4 6 2 2 2 1 1 2 1 3 1 4 2 3 2 4 3 4 --------------------- 答案应该是No,但是程序会跑出Yes。
点赞 回复 分享
发布于 2020-07-12 23:29
顶,我也想知道
点赞 回复 分享
发布于 2020-07-12 23:16

相关推荐

压力很大,面试官全程高压,问的问题不难,但是没有任何反馈,很慌张,也无算法。实习问了20分钟,一直问我你们做的有什么用,总时长一小时1.学校都有什么课程2.spring的ioc原理以及优点3.除了解耦还知道什么?4.springboot与spring区别,二者的源码看过没?Tomcat了解嘛?有没有具体看过5.spring的bean,面试官一直在重复一个思想问我懂不懂,完全没听过6.mybatis是干什么的?ibatis用过没?平常怎么写SQL?完全不写嘛?7.设计一个分布式双十一秒杀系统(前端,网关,缓存,数据库防超卖全设计)8.怎么做限流9.缓存与数据库一致性,你做异步要用户等你嘛?10.负载均衡怎么做11.多数据中心还是单数据中心,如果出现没卖完怎么做(到这完全不会了,面试官直接说换个话题吧)12.平常读书吗?13.上过哲学课嘛?14.兴趣爱好有没有15.对ai的看法16.来深圳有问题嘛?17.为什么不考研18.上大学带给了你什么?你提升在哪里,有没有具体的例子?反问:1.现在手机都有应用市场,应用宝怎么盈利?除了手机应用市场还是有人用,现在在做跨端,微软都有合作,之后会进军mac,主要做游戏,腾讯本身就是游戏大户。2.面试表现?整体评价一下会给到反馈。面完直接变HR面,今天HR面后,已经转为录用评估了,来牛客许个愿,暑期现在还没什么面试,希望能拿个offer之后再考虑要不要留在手子吧。
nunuking:三面压力这么大吗,面试的会议约了多长时间呀
面试问题记录
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务