ACM_Someone like you

  1 /*
  2 題意：軍隊坐bus去機場 n個節點（bus）m條公交通路（單向）
  3 每走一條路花時間1 問最少破壞幾個結點（是相關聯的的路都不能走)
  4 使軍隊在至少k時間不能到達機場。
  5 思路：求最小割（等于最大流）
  6 建(新)圖：弗洛伊德求出任意兩點最短路（dist[a][b]）
  7 核心判斷dist(1,a)+dist(b,n)之和滿足小于k 則建邊addedge(n+a,b,INF)
  8 
  9 addedge(i,i+n,1);//注意方向
 10 
 11 start=n+1，end=n;totals=n+n;
 12 sap();即可。
 13 */
 14 #include <iostream>
 15 #include<cstdio>
 16 #include<cstring>
 17 #include<vector>
 18 #include<queue>
 19 #include<algorithm>
 20 using namespace std;
 21 #define min(a,b) ((a)<(b))?(a):(b)
 22 #define max(a,b) ((a)>(b))?(a):(b)
 23 #define MAXN 6005//盡量開大點
 24 #define MAXM  100002 //M取N的平方倍或者N*9
 25 #define INF 0x3f3f3f3f
 26 int m,n;
 27 struct node
 28 {
 29     int n;//點編號
 30     int w;//點權
 31 }Node[MAXM];//n變m
 32 
 33 //鏈式前向星
 34 struct enode
 35 {
 36     int t;
 37     int w;                //權值
 38     int c;                //流量
 39 //  int cost;
 40 //    int pre;            //前向指針
 41     int next;
 42 };
 43 
 44     struct enode e[MAXM];
 45     int box[MAXN],ecnt;
 46     //int etail[MAXN];        //尾部
 47     void init()
 48     {
 49         ecnt=0;
 50         memset(box,-1,sizeof(box));
 51     //    memset(etail,-1,sizeof(etail));        //初始化尾部
 52     }
 53     void add(int s,int t)
 54     {
 55          e[ecnt].t=t;
 56          e[ecnt].next=box[s];
 57          box[s]=ecnt++;
 58     }
 59     void addedge(int f,int t,int c)            //流量重載
 60     {
 61         e[ecnt].next=box[f];
 62         e[ecnt].t=t;
 63         e[ecnt].c=c;
 64         box[f]=ecnt++;
 65         e[ecnt].next=box[t];
 66         e[ecnt].t=f;
 67         e[ecnt].c=0;
 68         box[t]=ecnt++;
 69     }
 70 int sap(int s,int t,int N)//最大流問題
 71 {
 72     int gap[MAXN],lvl[MAXN],cur[MAXN],pre[MAXN];
 73     int curflow,ans=0,u,tmp,neck,i;
 74     memset(lvl,0,sizeof(lvl));
 75     memset(gap,0,sizeof(gap));
 76     memset(pre,-1,sizeof(pre));
 77     for(i=0;i<N;i++)
 78         cur[i]=box[i];
 79     gap[0]=N;
 80     u=s;
 81     while(lvl[s]<N)
 82     {
 83         if(u==t)
 84         {
 85             curflow=INF;
 86             for(i=s;i!=t;i=e[cur[i]].t)
 87             {
 88                 if(curflow>e[cur[i]].c)
 89                 {
 90                     neck=i;
 91                     curflow=e[cur[i]].c;
 92                 }
 93             }
 94             for(i=s;i!=t;i=e[cur[i]].t)
 95             {
 96                 tmp=cur[i];
 97                 e[tmp].c-=curflow;
 98                 e[tmp^1].c+=curflow;
 99             }
100             ans+=curflow;
101             u=neck;
102         }
103         for(i=cur[u];i!=-1;i=e[i].next)
104             if(e[i].c && lvl[u]==lvl[e[i].t]+1)
105                 break;
106         if(i!=-1)
107         {
108             cur[u]=i;
109             pre[e[i].t]=u;
110             u=e[i].t;
111         }
112         else
113         {
114             if(--gap[lvl[u]]==0)
115                 break;
116              cur[u]=box[u];
117             for(tmp=N,i=box[u];i!=-1;i=e[i].next)
118                 if(e[i].c)
119                     tmp=min(tmp,lvl[e[i].t]);
120             lvl[u]=tmp+1;
121             gap[lvl[u]]++;
122             if(u!=s)
123                 u=pre[u];
124         }
125     }
126     return ans;
127 }
128 int dist[100][100];
129 int index[100][100];
130 void f()
131 {
132     int i,j,k;
133     for(i=1;i<=n;i++)
134     {
135         for(j=1;j<=n;j++)
136         {
137             for(k=1;k<=n;k++)
138             {
139                 if(dist[j][k]>dist[j][i]+dist[i][k]&&(j!=k))
140                 dist[j][k]=dist[j][i]+dist[i][k];
141             //松弛dist
142             }
143         }
144     }
145 }
146 int main()
147 {
148      int a,b,c,d,t,k,w,ct;
149      int i,j;
150      int start,end,ans;
151    while(scanf("%d%d%d",&n,&m,&k)&&n&&m&&k)
152    {
153        start=0;
154        end=n;
155        init();
156        memset(dist,INF,sizeof(dist));
157        memset(index,0,sizeof(index));
158        for(i=1;i<=n;i++)dist[i][i]=0;
159        for(i=1;i<=m;i++)
160        {
161            scanf("%d%d",&a,&b);
162            dist[a][b]=1;
163            index[a][b]=1;//標記通路索引
164        }
165        f();
166        for(i=1;i<=n;i++)
167        {
168            for(j=1;j<=n;j++)
169            {
170                if(index[i][j])//如果i 到 j是通路
171                {
172                    if(dist[1][i]+dist[j][n]<k)//該邊兩端的dist小于k
173                    addedge(i+n,j,INF);//流設為最大（未來應該可能被破壞的）
174                }//建立連接新節點 建新圖
175            }
176        }
177       for(i=1;i<=n;i++)addedge(i,i+n,1);//建新圖相連接的兩個節點流量為1
178       // printf("%d---->%d\n",i,dist[i][j]);
179       ans=sap(n+1,end,n*2);
180       if(ans>n)printf("%d\n",n);
181       else
182        printf("%d\n",ans);
183    }
184     return 0;
185 }
186 /*
187 
188 Sample Input
189 
190 5 7 3
191 1 3
192 3 4
193 4 5
194 1 2
195 2 5
196 1 4
197 4 5
198 0 0 0
199 
200 Sample Output
201 
202 2
203 */