首页 > 代码库 > poj 1966 Cable TV Network

poj 1966 Cable TV Network

2024-08-29 18:12:56   219人阅读

给出一个无向图，求该图的点连通度。

点连通度：最小割点集合中的顶点数。

0<=n=50.

最小割。

边连通度很好求，只需要随便固定源点枚举汇点求最小割取min即可。

点连通度采用点边转化的思想，将每个点拆点，入点与出点连边将点上的信息反映在边上。

每个点的入点向出点连一条容量为1的边。

每条边拆成两条有向边，对于有向边(u,v)从u的出点向v的入点连一条容量为正无穷的边。

n2枚举源点和汇点，最小割取min即为答案。

割掉入出点间的边相当于删掉该点。真正的边不能删掉，设成正无穷防割。

点连通度不能固定源点枚举汇点，因为源汇两点默认不在最小割点集合中，所以必须枚举源汇，

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int dian=105;
 8 const int bian=20005;
 9 const int INF=0x3f3f3f3f;
10 const int inf=100000;
11 int h[dian],ver[bian],val[bian],nxt[bian],ch[dian],cr[dian];
12 int n,m,tot,aa,bb,ans;
13 int S,T;
14 void add(int a,int b,int c){
15     tot++;ver[tot]=b;val[tot]=c;nxt[tot]=h[a];h[a]=tot;
16     tot++;ver[tot]=a;val[tot]=0;nxt[tot]=h[b];h[b]=tot;
17 }
18 bool tell(){
19     memset(ch,-1,sizeof(ch));
20     queue<int>q;
21     q.push(S);
22     ch[S]=0;
23     while(!q.empty()){
24         int t=q.front();
25         q.pop();
26         for(int i=h[t];i;i=nxt[i])
27             if(ch[ver[i]]==-1&&val[i]){
28                 ch[ver[i]]=ch[t]+1;
29                 q.push(ver[i]);
30             }
31     }
32     return ch[T]!=-1;
33 }
34 int zeng(int a,int b){
35     if(a==T)
36         return b;
37     int r=0;
38     for(int i=cr[a];i&&b>r;i=nxt[i])
39         if(ch[ver[i]]==ch[a]+1&&val[i]){
40             int t=zeng(ver[i],min(b-r,val[i]));
41             val[i]-=t,r+=t,val[i^1]+=t;
42             if(val[i])
43                 cr[a]=i;
44         }
45     if(!r)
46         ch[a]=-1;
47     return r;
48 }
49 int dinic(){
50     int r=0,t;
51     while(tell()){
52         for(int i=1;i<=n+n;i++)
53             cr[i]=h[i];
54         while(t=zeng(S,INF))
55             r+=t;
56     }
57     return r;
58 }
59 int main(){
60     while(scanf("%d%d",&n,&m)!=EOF){
61         memset(h,0,sizeof(h));
62         memset(nxt,0,sizeof(nxt));
63         tot=1;
64         ans=INF;
65         for(int i=1;i<=n;i++)
66             add(i,i+n,1);
67         for(int i=1;i<=m;i++){
68             scanf(" (%d,%d)",&aa,&bb);
69             add(aa+n+1,bb+1,inf);
70             add(bb+n+1,aa+1,inf);
71         }
72         for(int i=1;i<=n;i++)
73             for(int j=1;j<=n;j++){
74                 if(i==j)
75                     continue;
76                 S=i+n,T=j;
77                 ans=min(ans,dinic());
78                 for(int k=2;k<=tot;k+=2){
79                     val[k]+=val[k^1];
80                     val[k^1]=0;
81                 }
82             }
83         if(ans>=inf)
84             ans=n;
85         printf("%d\n",ans);
86     }
87     return 0;
88 }

 

poj 1966 Cable TV Network


联系
我们