POJ1966

Problem : Cable TV Network
Description : 求一个无向图的点连通度。
Solution : 拆点+最小割。这几乎是一个模板题。但是数据太逗比了，题中说了：“ Follow m data pairs (u,v), u < v”但是就是存在(1,1)这种类型的边。WA了一天才发现这个问题，如果存在这种边，就会导致拆点失败！。说说如何求无向图的点连通度吧。我们可以用网络最大流来做，首先要拆点连一条权值为1的边，如果删掉这条边也就等于删掉了这个点，那么直接对这个图求最小割就好了。
Code(C++) :

#include 
#include #include 
#include 
#include #define MIN(a,b) ((a)>(b)? (b):(a))using namespace std;const int SIZE=50*2+50;
const int INF=0x3f3f3f3f;struct Node{int u,v;int cap;Node(){}Node(int U,int V,int Cap):u(U),v(V),cap(Cap){}
};int src,des;
vector<int> G[SIZE];
Node e[SIZE*SIZE/2];
int d[SIZE];
int cur[SIZE];
int top;int N,M;
bool MAP[SIZE][SIZE];void addedge(int u,int v,int cap)
{G[u].push_back(top);e[top++]=Node(u,v,cap);G[v].push_back(top);e[top++]=Node(v,u,0);
}void build()
{   int i,j;for(i=0;i0;for(i=1;i<=N;i++)addedge(i+N,i,1);for(i=1;i<=N;i++)for(j=1;j<=N;j++)if(MAP[i][j])addedge(i,j+N,INF);
}bool bfs(int src,int des)
{memset(d,-1,sizeof(d));queue<int> que;que.push(src);d[src]=0;while(!que.empty()){int now=que.front();que.pop();for(int i=0;iif(tmp.cap>0&&d[tmp.v]==-1)d[tmp.v]=d[now]+1,que.push(tmp.v);}}return d[des]>=0;
}int dfs(int t,int sum,int des)
{if(t==des||!sum)return sum;int flow=0,f;for(int &i=cur[t];iif(d[tmp.v]==d[t]+1&&(f=dfs(tmp.v,MIN(sum,tmp.cap),des))>0){tmp.cap-=f;e[G[t].at(i)^1].cap+=f;sum-=f;flow+=f;if(!sum)break;}}return flow;
}int DINIC(int src,int des)
{int sum=0;while(bfs(src,des)){memset(cur,0,sizeof(cur));sum+=dfs(src,INF,des);}return sum;
}int main()
{//freopen("in.data","r",stdin);while(~scanf("%d%d",&N,&M)){int i,j;int ans=N;int x,y;memset(MAP,false,sizeof(MAP));for(i=0;iscanf(" (%d,%d)",&x,&y);++x,++y;if(x==y)continue;MAP[x][y]=MAP[y][x]=true;}for(i=1;i<=N;i++)for(j=i+1;j<=N;j++){build();addedge(0,i,INF);addedge(j+N,N*2+1,INF);int tmp=DINIC(0,2*N+1);ans=MIN(ans,tmp);}printf("%d\n",ans);}return 0;
}