首页 > 代码库 > NYIST 677 碟战

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_李如兵

 

解题:求最小割

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 210;18 struct arc{19     int to,flow,next;20     arc(int x = 0,int y = 0,int z = -1){21         to = x;22         flow = y;23         next = z;24     }25 };26 arc e[200000];27 int head[maxn],d[maxn],cur[maxn];28 int tot,S,T;29 void add(int u,int v,int flow){30     e[tot] = arc(v,flow,head[u]);31     head[u] = tot++;32     e[tot] = arc(u,0,head[v]);33     head[v] = tot++;34 }35 bool bfs(){36     queue<int>q;37     memset(d,-1,sizeof(d));38     d[S] = 1;39     q.push(S);40     while(!q.empty()){41         int u = q.front();42         q.pop();43         for(int i = head[u]; ~i; i = e[i].next){44             if(e[i].flow && d[e[i].to] == -1){45                 d[e[i].to] = d[u] + 1;46                 q.push(e[i].to);47             }48         }49     }50     return d[T] > -1;51 }52 int dfs(int u,int low){53     if(u == T) return low;54     int tmp = 0,a;55     for(int &i = cur[u]; ~i; i = e[i].next){56         if(e[i].flow > 0&& d[e[i].to] == d[u]+1 &&(a=dfs(e[i].to,min(low,e[i].flow)))){57             e[i].flow -= a;58             e[i^1].flow += a;59             tmp += a;60             low -= a;61             if(!low) break;62         }63     }64     if(!tmp) d[u] = -1;65     return tmp;66 }67 int dinic(){68     int ans = 0;69     while(bfs()){70         memcpy(cur,head,sizeof(head));71         ans += dfs(S,INF);72     }73     return ans;74 }75 int main() {76     int cs,n,m,p,u,v,cc = 1;77     scanf("%d",&cs);78     while(cs--){79         scanf("%d %d %d",&n,&m,&p);80         memset(head,-1,sizeof(head));81         S = 0;82         T = n;83         for(int i = tot = 0; i < p; ++i){84             scanf("%d",&u);85             add(S,u,INF);86         }87         for(int i = 0; i < m; ++i){88             scanf("%d %d",&u,&v);89             add(u,v,1);90             add(v,u,1);91         }92         printf("Case #%d: %d\n",cc++,dinic());93     }94     return 0;95 }
View Code

 

NYIST 677 碟战