NYIST 677 碟战

碟战
时间限制：2000 ms | 内存限制：65535 KB
难度：4

描述
知己知彼，百战不殆！在战争中如果被敌人掌握了自己的机密，失败是必然的。K国在一场战争中屡屡失败，就想到自己的某些城市可能会有敌方的间谍。
在仔细调查后，终于得知在哪些城市存在间谍。当然这个消息也被敌方间谍得知，所以间谍们开始撤离，试图到达K国唯一机场，然后抢夺飞机回国。由于城市内部比较复杂，K国领导人决定封锁道路，阻止所有间谍到达机场。城市编号为1~N，两个城市有不超过1条双向道路相连。机场在N号城市，不会有间碟。
由于要节约兵力，至少要封锁多少条道路才能阻止所有间谍到达机场？

输入
第一行包含一个整数T（T <= 100)，为测试数据组数。
接下来每组测试数据第一行包含三个整数n,m,p（2<= n <= 200,1< m < 20000,1 <= p < n),分别表示城市数量，道路数量，存在间谍的城市的数量。
接下来的一行包含p个整数x（1 <= x < n),表示存在间谍城市的编号。
接下来的m行，每行包含两个整数i,j，表示城市i与城市j有道路相通。

输出
输出“Case #i: ans”(不含引号),i为第i组数据，ans为需要封锁道路的条数。
样例输入
2
4 4 2
1 2
1 2
2 4
1 3
3 4
4 3 2
1 2
2 3
3 4
2 4

样例输出
Case #1: 2
Case #2: 2

来源
NYIST第一届校赛(专业组)

上传者
ACM_李如兵

解题：求最小割

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 struct arc{

     int to,flow,next;

     arc(int x = ,int y = ,int z = -){

         to = x;

         flow = y;

         next = z;

     }

 };

 arc e[];

 int head[maxn],d[maxn],cur[maxn];

 int tot,S,T;

 void add(int u,int v,int flow){

     e[tot] = arc(v,flow,head[u]);

     head[u] = tot++;

     e[tot] = arc(u,,head[v]);

     head[v] = tot++;

 }

 bool bfs(){

     queue<int>q;

     memset(d,-,sizeof(d));

     d[S] = ;

     q.push(S);

     while(!q.empty()){

         int u = q.front();

         q.pop();

         for(int i = head[u]; ~i; i = e[i].next){

             if(e[i].flow && d[e[i].to] == -){

                 d[e[i].to] = d[u] + ;

                 q.push(e[i].to);

             }

         }

     }

     return d[T] > -;

 }

 int dfs(int u,int low){

     if(u == T) return low;

     int tmp = ,a;

     for(int &i = cur[u]; ~i; i = e[i].next){

         if(e[i].flow > && d[e[i].to] == d[u]+ &&(a=dfs(e[i].to,min(low,e[i].flow)))){

             e[i].flow -= a;

             e[i^].flow += a;

             tmp += a;

             low -= a;

             if(!low) break;

         }

     }

     if(!tmp) d[u] = -;

     return tmp;

 }

 int dinic(){

     int ans = ;

     while(bfs()){

         memcpy(cur,head,sizeof(head));

         ans += dfs(S,INF);

     }

     return ans;

 }

 int main() {

     int cs,n,m,p,u,v,cc = ;

     scanf("%d",&cs);

     while(cs--){

         scanf("%d %d %d",&n,&m,&p);

         memset(head,-,sizeof(head));

         S = ;

         T = n;

         for(int i = tot = ; i < p; ++i){

             scanf("%d",&u);

             add(S,u,INF);

         }

         for(int i = ; i < m; ++i){

             scanf("%d %d",&u,&v);

             add(u,v,);

             add(v,u,);

         }

         printf("Case #%d: %d\n",cc++,dinic());

     }

     return ;

 }

巴特西

NYIST 677 碟战

最新文章

热门文章