大致题意:
给出一个又n个点,m条边组成的无向图。给出两个点s,t。对于图中的每个点,去掉这个点都需要一定的花费。求至少多少花费才能使得s和t之间不连通。
大致思路:
最基础的拆点最大流,把每个点拆作两个点 i 和 i' 连接i->i'费用为去掉这个点的花费,如果原图中有一条边a->b则连接a'->b。对这个图求出最大流即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int inf=1<<30;
const int nMax=10105;
const int mMax=3000000;
class node{
public:
int c,u,v,next;
};node edge[mMax];
int ne, head[nMax];
int cur[nMax], ps[nMax], dep[nMax];
void addedge(int u, int v,int w){ ////dinic邻接表加边
// cout<<u<<" add "<<v<<" "<<w<<endl;
edge[ne].u = u;
edge[ne].v = v;
edge[ne].c = w;
edge[ne].next = head[u];
head[u] = ne ++;
edge[ne].u = v;
edge[ne].v = u;
edge[ne].c = 0;
edge[ne].next = head[v];
head[v] = ne ++;
}
int dinic(int s, int t){ // dinic
int tr, res = 0;
int i, j, k, f, r, top;
while(1){
memset(dep, -1, sizeof(dep));
for(f = dep[ps[0]=s] = 0, r = 1; f != r;)
for(i = ps[f ++], j = head[i]; j; j = edge[j].next)
if(edge[j].c && dep[k=edge[j].v] == -1){
dep[k] = dep[i] + 1;
ps[r ++] = k;
if(k == t){
f = r; break;
}
}
if(dep[t] == -1) break;
memcpy(cur, head, sizeof(cur));
i = s, top = 0;
while(1){
if(i == t){
for(tr =inf, k = 0; k < top; k ++)
if(edge[ps[k]].c < tr)
tr = edge[ps[f=k]].c;
for(k = 0; k < top; k ++){
edge[ps[k]].c -= tr;
edge[ps[k]^1].c += tr;
}
i = edge[ps[top=f]].u;
res += tr;
}
for(j = cur[i]; cur[i]; j = cur[i] =edge[cur[i]].next){
if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break;
}
if(cur[i]){
ps[top ++] = cur[i];
i = edge[cur[i]].v;
}
else{
if(top == 0) break;
dep[i] = -1;
i = edge[ps[-- top]].u;
}
}
}
return res;
}
int main()
{
int i,j,a,b,c,s,t,m,n;
while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
{
ne=2;
memset(head,0,sizeof(head));
for(i=1;i<=n;i++)
{
scanf("%d",&a);
addedge(i,i+n,a);
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
addedge(a+n,b,inf);
addedge(b+n,a,inf);
}
int res=dinic(s,t+n);
printf("%d\n",res);
}
return 0;
}
分享到:
相关推荐
ACM/ICPC参赛者必备!模版库,数十页的C++代码,涵盖ACM/ICPC中出现的各种算法!此为吉林大学版,内容相对比较全,排版质量是各校的模板中最好的!
ACM/ICPC亚洲预赛成都赛区网络赛真题,分享给广大热衷于ACM的人们们!
acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 ...
The 36th ACM/ICPC Asia Regional Shanghai Site —— Online Contest Problem Set
ACM/ICPC2009 拉丁美洲区域赛 包含输入输出数据 题目PDF文档 详细解题报告+答案代码TXT文档 有一半是水题,2、3个比较难的 大家可以拿来做做 其中的输入输出数据,可以放到那个离线OJ系统去判断你的程序对错。(离线...
ACM/ICPC大赛
ACM/ICPC中国*辽宁第二届大学生程序设计竞赛题目
2010年ACM/ICPC珠海区域赛决赛题目
acm/icpc算法集合。acm/icpc算法集合。acm/icpc算法集合。
ACM/ICPC World Finals 1990 task
搜索
ACM/ICPC的教学与实践
浙江师范大学 ACM/ICPC 集训队――算法设计入门学习资料浙江师范大学 ACM/ICPC 集训队――算法设计入门学习资料
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
有关于2011华中南赛区ACM/ICPC程序设计邀请赛及“永新视博”杯程序设计大赛的解题报告,希望对名位有所帮助!!!!!
THE 30th ACM/ICPC ASIA REGIONAL 2005 HANGZHOU SITE Onsite Contest Session 8:30am – 13:30pm, November 20th 2005 (GMT+8) <br>知道是什么了吧。。。
ACM/ICPC模板 内容大概有这些 其他 --高精度模板 --RMQ --改点堆优化的dijkstra算法 --快速付利叶变换 --稳定婚姻问题 --SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --...
本代码包括了常见的ACM算法,并给出了详细地实现过程,并附上了ACM/ICPC 竞赛之STL。
北京大学多次承担ACM/ICPC亚洲区预选赛命题,广获好评。近几年负责命题的赛区有:2008年北京赛区,2009年宁波赛区,2010年杭州赛区,2010年福州赛区,2011年北京赛区,2011年福州赛区,2012年金华赛区,2012年杭州...