poj 1966(顶点连通度）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：给出一个n个节点和m条边的图，求该图的顶点连通度。

分析：顶点连通度的求解可以转换为网络最大流问题。

（1）原图G中的每个顶点v变成网络中的两个顶点v‘和v’‘，顶点v’至v''有一个条弧（有向边）连接，弧容量为1；

（2）原图G中的每条边e=uv，在网络中有两条弧e'=u''v',e''=v''u'与之对应，e'弧容量为oo（无穷），e''弧容量为oo(无穷)

（3）A''为源点，B'为汇点，枚举所有汇点，求最小割最小的那个

AC代码如下：

#include<cstdio>
#include<cstring>
const int N=+;
const int INF=0x3f3f3f3f;
struct EDGE{
int v,w,next;
}edge[N*N],edge2[N*N];
int g;
int first[N],numh[N],h[N],curedge[N],pre[N];
//int first[N],gap[N],pre[N],dis[N],cur[N];
int min(int a,int b)
{
return a<b?a:b;
}
void AddEdge(int u,int v,int w)
{
edge[g].v=v;
edge[g].w=w;
edge[g].next=first[u];
first[u]=g++;
edge[g].v=u; //反向边
edge[g].w=;
edge[g].next=first[v];
first[v]=g++;
}
int sap(int s,int t,int n,EDGE edge[])
{
int cur_flow,u,tmp,neck,i;
int flow_ans=;
memset(h,,sizeof(h));
memset(numh,,sizeof(numh));
memset(pre,-,sizeof(pre));
for(i=;i<n;i++)
curedge[i]=first[i];
numh[]=n;
u=s;
while(h[s]<n)
{
if(u==t)
{
cur_flow=INF+; //注意：要+1
for(i=s;i!=t;i=edge[curedge[i]].v)
{
if(cur_flow>edge[curedge[i]].w)
{
neck=i;
cur_flow=edge[curedge[i]].w;
}
}
for(i=s;i!=t;i=edge[curedge[i]].v)
{
tmp=curedge[i];
edge[tmp].w-=cur_flow;
edge[tmp^].w+=cur_flow;
}
flow_ans+=cur_flow;
u=neck;
}
for(i=curedge[u];i!=-;i=edge[i].next)
{
if(edge[i].w&&h[u]==h[edge[i].v]+)
break;
}
if(i!=-)
{
curedge[u]=i;
pre[edge[i].v]=u;
u=edge[i].v;
}
else
{
if(==--numh[h[u]])
break;
curedge[u]=first[u];
for(tmp=n,i=first[u];i!=-;i=edge[i].next)
{
if(edge[i].w)
tmp=min(tmp,h[edge[i].v]);
}
h[u]=tmp+;
numh[h[u]]++;
if(u!=s)
u=pre[u];
}
}
return flow_ans;
}
/*int cou;
int sap(int s,int t,int n,EDGE edge[])
{
memset(cur,0,sizeof(cur));
memset(pre,0,sizeof(pre));
int flow=0,i;
int u=pre[s]=s;
cou=n;
for(i=0;i<cou;i++)
{
cur[i]=first[i];
dis[i]=gap[i]=0;
}
gap[0]=cou;
int aug=INF;
while(dis[s]<cou)
{
bool flag=true;
for(int j=cur[u];j!=-1;j=cur[u]=edge[j].next){
int v=edge[j].v;
if(edge[j].w>0&&dis[u]==dis[v]+1)
{
flag=false;
pre[v]=u;
u=v;
if(aug>edge[j].w)
aug=edge[j].w;
if(u==t)
{
flow+=aug;
while(u!=s){
u=pre[u];
edge[cur[u]].w-=aug;
edge[cur[u]^1].w+=aug;
}
aug=INF;
}
break;
}
}
if(!flag)
continue;
int minh=cou;
for(int k=first[u];k!=-1;k=edge[k].next)
{
int v=edge[k].v;
if(edge[k].w>0&&minh>dis[v]){
minh=dis[v];
cur[u]=k;
}
}
if((--gap[dis[u]])==0)
break;
gap[dis[u]=minh+1]++;
u=pre[u];
}
return flow;
}*/
int main()
{
// printf("%d\n",INF);
int i,n,m,u,v,k;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(m==)
{
if(n==)
printf("1\n");
else
printf("0\n");
continue;
}
g=;
memset(first,-,sizeof(first));
for(i=;i<n;i++)
AddEdge(i,i+n,);
for(i=;i<m;i++)
{
scanf(" (%d,%d)",&u,&v);
AddEdge(u+n,v,INF);
AddEdge(v+n,u,INF);
}
int ans=INF;
for(i=;i<n;i++)
{
for(k=;k<g;k++)
edge2[k]=edge[k];
ans=min(ans,sap(+n,i,n*,edge2));
}
if(ans==INF)
ans=n;
printf("%d\n",ans);
}
return ;
}