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 */