P2944 [USACO09MAR]地震损失2Earthquake Damage 2

$P$个点,$C$条双向边。求最少删去几个点使$N$个给定的点与点$1$分开。

显然的最小割。

将点$i$套路地拆成$i_1,i_2$,割点转化成割边

对于点$1$:$link(S,1_1,inf),link(1_1,1_2,inf)$。保证不被割掉,且分到$S$割中

对于每个给定点$k$:$link(k_2,T,inf),link(k_1,k_2,inf)$。保证不被割掉,且分到$T$割中

对于每条双向边$(u,v)$:$link(u_1,v_2,inf),link(u_2,v_1,inf)$。保证不被割掉

对于剩余点:$link(i_1,i_2,1)$。可能被割掉

建好图跑遍最大流(最小割)就好辣

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 10005
#define M 100005
const int inf=2e9;
int n,S,T,d[N],cur[N];
queue <int> h; bool vis[N],e[N];
int cnt=,hd[N],nxt[M],ed[N],poi[M],val[M];
inline void adde(int x,int y,int v){
nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt,
ed[x]=cnt, poi[cnt]=y, val[cnt]=v;
}
inline void link(int x,int y,int v){adde(x,y,v),adde(y,x,);}
bool bfs(){
for(int i=;i<=T;++i) vis[i]=,cur[i]=hd[i];
h.push(S); vis[S]=;
while(!h.empty()){
int x=h.front(); h.pop();
for(int i=hd[x];i;i=nxt[i]){
int to=poi[i];
if(!vis[to]&&val[i]>)
vis[to]=,d[to]=d[x]+,h.push(to);
}
}return vis[T];
}
int dfs(int x,int a){
if(x==T||a==) return a;
int F=,f;
for(int &i=cur[x];i;i=nxt[i]){
int to=poi[i];
if(d[to]==d[x]+&&(f=dfs(to,min(a,val[i])))>)
a-=f,F+=f,val[i]-=f,val[i^]+=f;
if(!a) break;
}return F;
}
int dinic(){int re=; while(bfs())re+=dfs(S,inf); return re;}
int main(){
int m,c,q1,q2;
scanf("%d%d%d",&n,&m,&c);
S=n*+; T=S+;
link(S,,inf); link(,+n,inf);
while(m--){
scanf("%d%d",&q1,&q2);
link(q1+n,q2,inf);
link(q2+n,q1,inf);
}
while(c--){
scanf("%d",&q1); e[q1]=;
link(q1,q1+n,inf);
link(q1+n,T,inf);
}
for(int i=;i<=n;++i)
if(!e[i]) link(i,i+n,);
printf("%d",dinic());
return ;
}

最新文章

  1. dotNet平台模板列中的单选无效的解决方案
  2. The Number Off of FFF
  3. URL编码知识摘抄备忘
  4. 解读Unity中的CG编写Shader系列八(多光源漫反射)
  5. jvm运行机制与内存管理
  6. 最新Velocity使用和Velocity语法
  7. iOS 开发获取唯一标识
  8. SQL的主键和外键约束
  9. 异步I/O
  10. ASP.NET方面的一些经典文章收集
  11. 安卓高手之路之 WindowManager
  12. poj 1236 Network of Schools(连通图入度,出度为0)
  13. c++内联函数与静态函数
  14. CentOS6.5 mini开启网络
  15. hdu1159 LCS模板题
  16. sizeof(extern类型数组)
  17. volitale、synchronized、RetreenLock区别
  18. 移动开发的捷径:3种方式轻松创建webapp
  19. hadoop_随笔二_参数
  20. Windows与系统信息相关的DOS命令

热门文章

  1. Spring_搭建过程中遇到的问题
  2. sigprocmask()函数学习笔记
  3. CF 82 D.Two out of Three
  4. robotframework关键字
  5. count(*),count(1),count(列名)的区别
  6. 企业级监控软件zabbix搭建部署之zabbix server的安装
  7. Python操作cx_Oracle笔记
  8. Oracle12c创建及删除PDB
  9. python+selenium+pytest+html报告
  10. php长连接和短连接的使用场景