性质一·任何一对顶点间==0和其他顶点间。
考虑0到1有三条路径A1,A2,A3,0到2有三条B1,B2,B3。
A1+B1就是一条从1到2很好的路径。（没有重合点）
他们之间最多会有两条路径有相同顶点，此时只需要从重合的点开始走即可。（有）
---------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define MAX_N 550
#define MAX_M 50050

using namespace std;
 
vector<int> G[MAX_N];
int match[MAX_N];
bool matchdst[MAX_N], vis[MAX_N];

int dfs(int from, int to) {
	for (int i = G[from].size() - 1;i >= 0;--i) {
		int v = G[from][i];
		if (v == to) {
			if (matchdst[from]) continue;
			matchdst[from] = true;
			return true;
		}
		if (vis[v]) continue;
		vis[v] = true;
		if (dfs(match[v], to)) {
			match[v] = from;
			return true;
		}
	}
	return false;
}

bool flow(int from, int to, int n) {
	for (int i = 0;i < n;++i) match[i] = i;
	memset(matchdst, 0, sizeof(matchdst));
	for (int i = 0;i < 3;++i) {
		memset(vis, 0, sizeof(vis));
		if (!dfs(from, to)) return false;
	}
	return true;
}

bool solve(int n, int m) {
	for (int i = 1;i < n;++i) 
		if (!flow(0, i, n)) return false;
	return true;
}

int main(int argc,char *argv[]) {
	int n, m;
	while (true) {
		scanf("%d%d", &n, &m);
		if (n == 0 && m == 0) break;
		for (int i = 0;i < n;++i) G[i].push_back(i);
		for (int i = 0, a, b;i < m;++i) {
			scanf("%d%d", &a, &b);
			G[a].push_back(b), G[b].push_back(a);
		}
		bool ans = solve(n, m);
		printf("%s\n", ans ? "YES" : "NO");
		for (int i = 0;i < n;++i) G[i].clear();
	}
	return 0;
}

• Re:搬运一个网络流代码（非原创） (1695) 20051106 2017-01-15 10:55:29