绝对难度虚高的一题

看到题目,至少损坏几个房子,开始考虑最小割,建的是双向边,所以拆点,边权除了自己与自己的之外都连inf。然后把所有求救的点都连到超级源上,跑一遍最大流就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define inf 50000000
#define re register
using namespace std;
struct po
{
int to,dis,nxt;
}edge[];
int head[],cur[],dep[],n,m,s,t,u,num=-,x,y,l,tot,sum,k;
inline int read()
{
int x=,c=;
char ch=' ';
while((ch>''||ch<'')&&ch!='-')ch=getchar();
while(ch=='-')c*=-,ch=getchar();
while(ch<=''&&ch>='')x=x*+ch-'',ch=getchar();
return x*c;
}
inline void add_edge(int from,int to,int dis)
{
edge[++num].nxt=head[from];
edge[num].to=to;
edge[num].dis=dis;
head[from]=num;
}
inline void add(int from,int to,int dis)
{
add_edge(from,to,dis);
add_edge(to,from,);
}
inline bool bfs()
{
memset(dep,,sizeof(dep));
queue<int> q;
while(!q.empty())
q.pop();
dep[s]=;
q.push(s);
while(!q.empty())
{
int now=q.front();
q.pop();
for(re int i=head[now];i!=-;i=edge[i].nxt)
{
int v=edge[i].to;
if(dep[v]==&&edge[i].dis>)
{
dep[v]=dep[now]+;
if(v==t)
return ;
q.push(v);
}
}
}
return ;
}
inline int dfs(int u,int dis)
{
if(u==t)
return dis;
int diss=;
for(re int& i=cur[u];i!=-;i=edge[i].nxt)
{
int v=edge[i].to;
if(dep[v]==dep[u]+&&edge[i].dis!=)
{
int check=dfs(v,min(dis,edge[i].dis));
if(check>)
{
diss+=check;
dis-=check;
edge[i].dis-=check;
edge[i^].dis+=check;
if(dis==) break;
}
}
}
return diss;
}
inline int dinic()
{
int ans=;
while(bfs())
{
for(re int i=;i<=*n;i++)
cur[i]=head[i];
while(int d=dfs(s,inf))
ans+=d;
}
return ans;
}
int main()
{
memset(head,-,sizeof(head));
n=read();m=read();k=read();
s=;t=;
for(re int i=;i<=m;i++)
{
x=read();y=read();
if(x!=y)
{
add(x+n,y,inf);
add(y+n,x,inf);
}
}
for(re int i=;i<=k;i++)
{
x=read();
add(s,x+n,inf);
}
for(re int i=;i<=n;i++)
add(i,i+n,);
cout<<dinic();
}

最新文章

  1. 《python核心编程》笔记——文件的创建、读取和显示
  2. linux下gimp的使用
  3. InfoSet
  4. Anysys Fluent安装教程
  5. js中获取样式的俩种方法 style.color和style[&#39;color&#39;] 区别
  6. (笔记)angular material radio用法
  7. 数据结构——Java实现二叉树
  8. JS-string内置对象
  9. SilkTest Q&amp;A 10
  10. 加载DLL模块
  11. Linux常用命令(一)--系统命令
  12. Jqurey 得到url参数 getUrlParam
  13. Android实时直播,一千行java搞定不依赖jni,延迟0.8至3秒,强悍移动端来袭
  14. 通过类创建子线程&amp;同步锁
  15. SqlServer 四大排名函数(ROW_NUMBER、RANK、DENSE_RANK、NTILE)简介
  16. 模板学习实践二 pointer
  17. 用ASP.NET实现下载远程图片保存到本地的方法 保存抓取远程图片的方法
  18. PHP重载以及Laravel门面Facade
  19. 48. Rotate Image (Array)
  20. 规则引擎之easyRules

热门文章

  1. 69、ViewPagerIndicator+ViewPager实现Tab
  2. Eclipse修改背景颜色
  3. centos6.5下安装samba服务器与配置
  4. [LintCode] 全排列
  5. angularJS中的ng-show、ng-if指令
  6. Java读取、创建Excel;验签,加密
  7. PIP源使用国内镜像
  8. 在Scrapy中使用IP池或用户代理(python3)
  9. SpringMVC 之 RESTful 风格的增删改查
  10. CentOS7.1 KVM虚拟化之linux虚拟机安装(2)