POJ1087 DInic

n个插座，m个电器，k个适配器。
建图：
原点s到电器容量1
电器到插座容量1
插座到终点容量1
插座到适配器容量inf
要哭出来了。。。。。要建双向边！！！！不过方向容量0
View Code
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<algorithm>
  4 #include<map>
  5 #include<iostream>
  6 #include<string>
  7 using namespace std;
  8 const int maxn = 505;
  9 const int maxm = 20005;
 10 const int inf = 99999999;
 11 int cnt,head1[ maxn ];
 12 int rece[ maxn ];
 13 struct node{
 14     int from,to,val,next;
 15 }edge[ maxm ];
 16 map<string,int>mp;
 17 int s,t;
 18 void init(){
 19     cnt=0;
 20     mp.clear();
 21     memset( head1,-1,sizeof( head1 ));
 22 }
 23 void addedge( int a,int b,int c ){
 24     edge[ cnt ].from=a;
 25     edge[ cnt ].to=b;
 26     edge[ cnt ].val=c;
 27     edge[ cnt ].next=head1[ a ];
 28     head1[ a ]=cnt++;
 29     edge[ cnt ].from=b;
 30     edge[ cnt ].to=a;
 31     edge[ cnt ].val=0;
 32     edge[ cnt ].next=head1[ b ];
 33     head1[ b ]=cnt++;
 34 }
 35 int queue[ 1005 ];
 36 int lev[ maxn ];
 37  int Dinic( int start,int end ){
 38      int max_flow=0;
 39      while(true){
 40         // printf("dinic100\n");
 41          int head,tail,id,i;
 42          head=tail=0;
 43          queue[tail++]=start;//队列从0开始，tail指向下一个入队元素的位置,head指向出队元素
 44          memset(lev,-1,sizeof(lev));
 45          lev[start]=0;
 46          while(head<tail){
 47              id=head1[queue[head++]];
 48              while(id!=-1){
 49                 // printf("dinic200\n");
 50                  if(edge[id].val>0&&lev[edge[id].to]==-1){
 51                      lev[edge[id].to]=lev[edge[id].from]+1;
 52                      queue[tail++]=edge[id].to;
 53                      if(edge[id].to==end){
 54                          head=tail;
 55                          break;//end of while(head<tail)
 56                      }
 57                  }
 58                  id=edge[id].next;
 59              }
 60          }//分层，直到找到end为止，分层结束
 61  
 62          if(lev[end]==-1)
 63              break;//end of while(true)
 64  
 65          id=start;
 66          tail=0;
 67          while(true){//寻找增广路
 68         //     printf("dinic300\n");
 69              if(id==end){//找到了一条增广路
 70                  int flow=inf,flag=-1;
 71                  for(i=0;i<tail;i++){
 72                      if(edge[queue[i]].val<flow){
 73                          flag=i;
 74                          flow=edge[queue[i]].val;
 75                      }
 76                  //寻找最短的
 77                  }
 78                      for(i=0;i<tail;i++){
 79                         // printf("%d ",edge[queue[i]].from);
 80                          edge[queue[i]].val-=flow;
 81                          edge[queue[i]^1].val+=flow;
 82                      }
 83                     // printf("\nmax_flw:%d\n",max_flow);
 84                      if(flag!=-1){
 85                          max_flow+=flow;
 86                          tail=flag;
 87                          id=edge[queue[flag]].from;
 88                      }
 89                      else
 90                          return inf;
 91              }
 92              id=head1[id];
 93              while(id!=-1){
 94                 // printf("dinic400\n");
 95                  if(edge[id].val>0&&(lev[edge[id].from]+1==lev[edge[id].to]))
 96                      break;
 97                  id=edge[id].next;
 98              }
 99              if(id!=-1){
100                  queue[tail++]=id;
101                  id=edge[id].to;
102              }
103              else{
104                  if(tail==0)
105                      break;
106                  lev[edge[queue[tail-1]].to]=-1;
107                  id=edge[queue[--tail]].from;
108              } 
109          }
110      }
111      return max_flow;
112  }
113  
114 
115 int main(){
116     int n,m,k;
117     string name,pname;
118     while( scanf("%d",&n)!=EOF ){
119         init();
120         s=0;
121         int CNT=1;
122         for( int i=0;i<n;i++ ){
123             cin>>name;
124             mp[ name ]=CNT;
125             CNT++;
126         }
127         scanf("%d",&m);
128         int t1,t2;
129         int tot=m;
130         while( m-- ){
131             cin>>name>>pname;
132             if( mp[ name ]==0 ){
133                 mp[ name ]=CNT;
134                 t1=CNT;
135                 CNT++;
136             }
137             else
138                 t1=mp[ name ];
139             if( mp[ pname ]==0 ){
140                 mp[ pname ]=CNT;
141                 t2=CNT;
142                 CNT++;
143             }
144             else
145                 t2=mp[ pname ];
146             addedge( s,t1,1 );
147             addedge( t1,t2,1 );
148         }
149         scanf("%d",&k);
150         while( k-- ){
151             cin>>name>>pname;
152             if( mp[ name ]==0 ){
153                 mp[ name ]=CNT;
154                 t1=CNT;
155                 CNT++;
156             }
157             else
158                 t1=mp[ name ];
159             if( mp[ pname ]==0 ){
160                 mp[ pname ]=CNT;
161                 t2=CNT;
162                 CNT++;
163             }
164             else
165                 t2=mp[ pname ];
166             addedge( t1,t2,inf );
167         }
168         for( int i=1;i<=n;i++ )
169             addedge( i,maxn-1,1 );
170 
171         int ans=Dinic( 0,maxn-1 );
172         printf("%d\n",tot-ans);
173     }
174     return 0;
175 }
keep moving...