UVA 1660 Cable TV Network（最大流）

題意：給一個n個點的無向圖，求它的點連通度，即最少删除多少個點，使得圖不連通

思路：求點連通度，邊連通度都可以轉化為網絡流來做，拆點如果有U->V，那麼連U+N->V和V+N->U,然後枚舉源點彙點求最大流即可

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
const int maxn = 1000;
struct Edge
{
	int from,to,cap,flow;
	Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
struct Dinic
{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int> G[maxn];
	bool vis[maxn];
	int d[maxn];
	int cur[maxn];
	void AddEdge(int from,int to,int cap)
	{
		edges.push_back(Edge(from,to,cap,0));
		edges.push_back(Edge(to,from,0,0));
		m = edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	void init(int n)
	{
		for (int i = 0;i<=n;i++)
			G[i].clear();
		edges.clear();
	}
	bool BFS()
	{
		memset(vis,0,sizeof(vis));
		queue<int>q;
		q.push(s);
		d[s]=0;
		vis[s]=1;
		while (!q.empty())
		{
			int x = q.front();
			q.pop();
			for (int i = 0;i<G[x].size();i++){
				Edge &e = edges[G[x][i]];
				if (!vis[e.to] && e.cap>e.flow){
					vis[e.to]=1;
					d[e.to]=d[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<G[x].size();i++){
			Edge&e = edges[G[x][i]];
			if (d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0){
				e.flow+=f;
				edges[G[x][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if (a==0)
					break;
			}
		}
		return flow;
	}

	int Maxflow(int s,int t)
	{
		this->s=s;
		this->t=t;
		int flow = 0;
		while (BFS())
		{
			memset(cur,0,sizeof(cur));
			flow+=DFS(s,INF);
		}
		return flow;
	}
}di;
int uu[maxn],vv[maxn];
void addedge(int n,int m)
{
	di.init(2*n+2);
	for (int i = 1;i<=n;i++)
		di.AddEdge(i,i+n,1);
	for (int i = 0;i<m;i++)
	{
		di.AddEdge(uu[i]+n,vv[i],INF);
		di.AddEdge(vv[i]+n,uu[i],INF);
	}
}
int main()
{
	int n,m;
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		di.init(2*n+2);
		for (int i = 0;i<m;i++)
		{
            int u,v;
			scanf(" (%d,%d)",&uu[i],&vv[i]);
			uu[i]++,vv[i]++;
		}
		int ans = INF;
		for (int i = 1;i<=n;i++)
			for (int j = 1;j<=n;j++)
				if (i==j)
					continue;
		        else
				{
                    addedge(n,m);
					ans = min(ans,di.Maxflow(i+n,j));
				}
		if (ans == INF)
			ans = n;
		printf("%d\n",ans);
	}
}