571
poj 1966 Cable TV Network 點聯通度
求點聯通度，就是求圖中最大獨立軌的最小值，把點拆成2個v',v''，v‘->v''容量為1,u-v的一條邊就變為u''->v'和v''->u'兩個容量為無窮的邊，求s‘’ 到e'最大流即可
第一次寫dinic，沒帶當前弧優化，但對這題來說時間已經夠了
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
#define inf 1E9
int c[105][105],f[105][105];
int s,e;
int n;
int ans=0;
int vis[105];
int level[105];
queue<int> q;
int bfs()
{
while(!q.empty())q.pop();
q.push(s);
memset(level,0,sizeof(level));
level[s]=1;
int u,v;
while(!q.empty())
{
u=q.front();
q.pop();
for(v=0; v<n; v++)
{
if(!level[v]&&c[u][v]>f[u][v])
level[v]=level[u]+1,q.push(v);
}
}
return level[e];//gap
}
int dfs(int v,int flow)
{
if(!flow)return 0;
if(v==e)
{
ans+=flow;
return flow;
}
int t,last=flow;
for(int u=0; u<n; u++)
{
if((level[u]==level[v]+1)&&c[v][u]>f[v][u])//最短增廣路
{
t=dfs(u,min(flow,c[v][u]-f[v][u]));
f[v][u]+=t;
f[u][v]-=t;
flow-=t;
if(!flow)break;
}
}
return last-flow;
}
int main()
{
int m;
while(~scanf("%d%d",&n,&m))
{
int i,j,a,b;
memset(c,0,sizeof(c));
memset(f,0,sizeof(f));
for(i=0; i<n; i++)
c[i+n][i]=1;
for(i=0; i<m; i++)
{
scanf(" (%d,%d)",&a,&b);
c[b][a+n]=c[a][b+n]=inf;//拆點
}
n=n<<1;
ans=0;
memset(vis,0,sizeof(vis));
int t=n/2,Max=t;
for(i=0; i<t; i++)
for(j=i+t+1; j<n; j++)
{
if(c[i][j])continue;
memset(f,0,sizeof(f));
e=j;
s=i;
ans=0;
while(bfs())dfs(i,inf);
Max=min(ans,Max);
}
printf("%d\n",Max);
}
}
最後更新：2017-04-03 16:48:59