n<=3000个点m<=20000条无向边的图,有p<=n个出发点,每个出发点都不可拆,现拆一些点使每个出发点都不能到达点1,求最小点数。

简单的最小割。每个点拆成两个x和y,无向边A--B即Ay->Bx,By->Ax,每个点拆成的x和y再连边容量1,然后建超级源向p个点连边,最大流,没了。

错误。没看题。p个点不可割。WA了一发。正确做法只要把p个点的x->y的边容量设inf即可。

 #include<stdio.h>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<math.h>
//#include<iostream>
using namespace std; int n,m,p;
#define maxn 6011
#define maxm 100011
const int inf=0x3f3f3f3f;
struct Network
{
struct Edge{int to,next,cap,flow;}edge[maxm];
int first[maxn],le,n;
void clear(int n)
{
memset(first,,sizeof(first));
le=;this->n=n;
}
void in(int x,int y,int cap)
{
Edge &e=edge[le];
e.to=y;e.cap=cap;e.flow=;
e.next=first[x];first[x]=le++;
}
void insert(int x,int y,int cap)
{
in(x,y,cap);
in(y,x,);
}
int s,t,que[maxn],head,tail,dis[maxn],cur[maxn];
bool bfs()
{
memset(dis,,sizeof(dis));
dis[s]=;
que[head=(tail=)-]=s;
while (head!=tail)
{
const int now=que[head++];
for (int i=first[now];i;i=edge[i].next)
{
Edge &e=edge[i];
if (e.cap>e.flow && !dis[e.to])
{
dis[e.to]=dis[now]+;
que[tail++]=e.to;
}
}
}
return dis[t];
}
int dfs(int x,int a)
{
if (x==t || !a) return a;
int flow=,f;
for (int &i=cur[x];i;i=edge[i].next)
{
Edge &e=edge[i];
if (dis[e.to]==dis[x]+ && (f=dfs(e.to,min(a,e.cap-e.flow)))>)
{
e.flow+=f;
edge[i^].flow-=f;
flow+=f;
a-=f;
if (!a) break;
}
}
return flow;
}
int Dinic(int s,int t)
{
this->s=s,this->t=t;
int flow=;
while (bfs())
{
for (int i=;i<=n;i++) cur[i]=first[i];
flow+=dfs(s,0x3f3f3f3f);
}
return flow;
}
}g;
int x,y;int vis[maxn];
int main()
{
scanf("%d%d%d",&n,&m,&p);
g.n=(n<<)^;int s=g.n,t=;
for (int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
g.insert(x+n,y,inf);
g.insert(y+n,x,inf);
}
memset(vis,,sizeof(vis));
for (int i=;i<=p;i++)
{
scanf("%d",&x);vis[x]=;
g.insert(s,x,inf);
}
for (int i=;i<=n;i++) if (!vis[i]) g.insert(i,i+n,);else g.insert(i,i+n,inf);
printf("%d\n",g.Dinic(s,t));
return ;
}

最新文章

  1. 服务器asp.net 3.5 HTTP 错误 500.19 - Internal Server Error 无法访问请求的页面,因为该页的相关配置数据无效。
  2. cnodejs社区论坛6--评论功能
  3. Nginx重新编译添加模块
  4. 关于app.config不能即时保存读取的解决方案
  5. xdebug和xhprof
  6. SpringMvc入门二----HelloWorld
  7. Jq 遍历 全选 全不选 反选
  8. 自定义listView添加滑动删除功能
  9. OCaml Language Sucks
  10. ViewGroup可实现上下、各地跑马灯效果滚动
  11. linux集群批量执行命令
  12. gogogo
  13. [BZOJ1010] [HNOI2008] 玩具装箱toy (斜率优化)
  14. Django_创建项目
  15. Golang微服务:Micro介绍
  16. 搞Java的年薪 40W 是什么水平?
  17. LeetCode(85):最大矩形
  18. 固态硬盘使用简要手册&mdash;&mdash;windows平台
  19. style和getComputedStyle(ff)和currentStyle
  20. MATLAB 不能保存变量问题及解决办法

热门文章

  1. python2和python3的区别(转)
  2. Android iconfont字体图标的使用
  3. SQL Server 查询锁表和接锁表
  4. 里特定律 - Little&#39;s Law
  5. 错误消息 This computer doesn&#39;t have VT-X/AMD-v enabled
  6. (转)Spring的bean管理(注解方式)
  7. jsp公共头信息的抽取(相对路径的修改)
  8. Elasticsearch 索引管理和内核探秘
  9. [LOJ] 分块九题 2
  10. RAID磁盘阵列及CentOS7启动流程