最小割算法在电缆电视网络中的应用——UVA1660与POJ1966问题分析

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 
 7 using namespace std;
 8 
 9 const int N=100+3,M=3000+3;
10 const int INF=0x3f3f3f3f;
11 
12 struct edge{
13     int nxt,to,fl;
14 }ed[M];
15 
16 int head[N],cur;
17 int s,t;
18 queue<int>q;
19 int cap[N],fr[N];
20 
21 void add_edge(int l,int r,int f)
22 {
23     ed[cur]=(edge){head[l],r,f};
24     head[l]=cur++;
25     ed[cur]=(edge){head[r],l,0};
26     head[r]=cur++;
27 }
28 
29 int n,m;
30 int get;
31 bool ek()
32 {
33     memset(cap,0,sizeof(cap));
34     cap[s]=INF;
35     while(!q.empty())q.pop();
36     q.push(s);
37     while(!q.empty())
38     {
39         int u=q.front();q.pop();
40         for(int i=head[u];i!=-1;i=ed[i].nxt)
41             if(!cap[ed[i].to]&&ed[i].fl)
42                 cap[ed[i].to]=min(cap[u],ed[i].fl),
43                 fr[ed[i].to]=i,
44                 q.push(ed[i].to);
45         if(cap[t])break;
46     }
47     if(!cap[t])return 0;
48     get+=cap[t];
49     for(int u=t;u!=s;u=ed[fr[u]^1].to)
50         ed[fr[u]].fl-=cap[t],
51         ed[fr[u]^1].fl+=cap[t];
52     return 1;
53 }
54 
55 
56 
57 int l[M],r[M];
58 int main()
59 {
60     while(scanf("%d %d",&n,&m)!=EOF)
61     {
62         for(int i=1;i<=m;i++)
63             scanf(" (%d,%d)",&l[i],&r[i]);
64         int ans=n;
65         for(s=0;s)
66             for(t=s+1;t)
67             {
68                 memset(head,0xff,sizeof(head));
69                 cur=0;
70                 get=0;
71                 for(int i=1;i<=m;i++)
72                     add_edge(l[i],r[i]+n,n),
73                     add_edge(r[i],l[i]+n,n);
74                 for(int i=0;i)
75                     if(i==t||i==s)
76                         add_edge(i+n,i,n);
77                     else
78                         add_edge(i+n,i,1);
79                 while(ek());
80                 ans=min(ans,get);
81             }
82         cout83     }
84     return 0;
85 }[]