地震破坏
时间限制: 1 Sec 内存限制: 128 MB
题目描述
威斯康星发生了一场地震！约翰的牧场遭到了打击，有一些牛棚变成了废墟，如果一间牛棚遭到
了破坏，那么所有和它相连的道路都不能使用了。
约翰有 N 个牛棚，编号为 1 到 N，有 M 条双向道路连接这些牛棚，第 i 条道路连接的牛棚是
A i 和 B i ，A i 可能等于 B i ，也可能有多条道路连接同一对牛棚。
约翰让奶牛们集中到 1 号牛棚避难。有 P 头奶牛通过手机向约翰求救，她们的遭遇类似：好消
息是她们所在的牛棚没有损坏，坏消息是由于其他的牛棚遭到破坏，所以她们找不到任何可以走到 1
号牛棚的路径。假设发送报告的第 i 头奶牛目前在牛棚 R i 里，那么以最乐观的情况来看，至少有多
少牛棚被破坏了呢？
输入
• 第一行：三个整数 N，M 和 P, 1 ≤ P ≤ N ≤ 3000, 1 ≤ M ≤ 20000
• 第二行到第 M + 1 行：第 i + 1 行有两个整数 A i 和 B i ，1 ≤ A i ,B i ≤ N
• 第 M + 2 行到第 M + P + 1 行：第 i + M + 1 行有一个整数 R i , 1 ≤ R i ≤ N，保证每个 R i 都
是不同的
输出
• 单个整数：表示至少有几个牛棚被破坏了
样例输入
5 5 2
1 2
2 3
3 5
2 4
4 5
4
5
样例输出
1
提示
最乐观的情况是只有 2 号牛棚坏了
题解：
一道比较经典的最小割，首先因为每次删除的是一个点，所以要将每个点拆开，将1节点和打电话过来的几个节点残量设为最大值，其余的为1。（为了让割边落在可以去掉的点上）这样就可以将去点转化为割边。
然后根据图的连接方式，若节点x被分为x1和x2，节点y被分为y1和y2。若x和y连接，则将x2连y1，y2连x1，残量都为最大值。
然后跑一遍网络流就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#define inf (2e8)
using namespace std;
int n,m,l;
struct node
{
int next,to,cap;
}edge[];
int head[],size=,a[];
void putin(int from,int to,int cap)
{
size++;
edge[size].next=head[from];
edge[size].to=to;
edge[size].cap=cap;
head[from]=size;
}
void in(int from,int to,int cap)
{
putin(from,to,cap);
putin(to,from,);
}
int dist[],numbs[];
void bfs(int src,int des)
{
int i;
queue<int>mem;
mem.push(des);
dist[des]=;numbs[]++;
while(!mem.empty())
{
int x=mem.front();mem.pop();
for(i=head[x];i!=-;i=edge[i].next)
{
int y=edge[i].to;
if(edge[i].cap==&&dist[y]==&&y!=des)
{
dist[y]=dist[x]+;
numbs[dist[y]]++;
mem.push(y);
}
}
}
return;
}
int dfs(int src,int flow,int des)
{
if(src==des)return flow;
int i,low=,mindist=n*+;
for(i=head[src];i!=-;i=edge[i].next)
{
int y=edge[i].to;
if(edge[i].cap)
{
if(dist[y]==dist[src]-)
{
int t=dfs(y,min(flow-low,edge[i].cap),des);
edge[i].cap-=t;
edge[i^].cap+=t;
low+=t;
if(dist[src]>=n*+)return low;
if(low==flow)break;
}
mindist=min(mindist,dist[y]+);
}
}
if(!low)
{
if(!(--numbs[dist[src]]))dist[]=n*+;
++numbs[dist[src]=mindist];
}
return low;
}
int ISAP(int src,int des)
{
int ans=;
bfs(src,des);
while(dist[]<n*+)ans+=dfs(src,2e8,des);
return ans;
}
int main()
{
int i,j;
memset(head,-,sizeof(head));
scanf("%d%d%d",&n,&m,&l);
for(i=;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
in(n+from,to,inf);
in(n+to,from,inf);
}
for(i=;i<=l;i++){scanf("%d",&j);a[j]=;}
in(,n+,inf);
for(i=;i<=n;i++)
{
if(a[i]==){in(i,n+i,inf);in(n+i,*n+,inf);}
else in(i,n+i,);
}
in(,,inf);
int maxflow=ISAP(,n*+);
cout<<maxflow;
return ;
}