ACM确实是需要毅力的东西,最近刷网络流,竭尽全力的一个ac。。。
把题目中的模型转换成最小割模型,然后就是模版了
为什么是最小割?因为显然任意一个割中模块只能多放不能少,而满足条件的一定是一个割,所以满足条件的就是极小割,所有极小割也满足条件,最小割是极小割,所以花费最小的就是最小割
但是却百思不得其解的tle了,纠结,死都发现不了前几天自己写的那个模版里有什么问题,多路增广啊,gap优化也用了啊。。ac不能。。。纠结的一塌糊涂。。。然后怀疑是vector的问题,但是有人用vector ac了啊!!!
搞了2,3个小时,最后决定重敲一遍,凭着自己的感觉,在愤怒之下。。。在即将放弃dinic和stl下。。。在编译都没编译的情况下。。。提交了。。奇迹般的ac了。。最后发现是建图的地方写错了。。汗!!确实。。邻接表建图那里真坑爹!!这寒假都没干什么,时间就这样木有了。。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iomanip>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=21111;
struct zz
{
int from;
int to;
int c;
int id;
}zx,tz;
vector<zz>g[maxn];
queue<int>q;
int cen[maxn];
int n,m,s,t;
bool bfs()
{
while(!q.empty())
{
q.pop();
}
memset(cen,-1,sizeof(cen));
q.push(0);
cen[0]=0;
int now,to;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<g[now].size();i++)
{
to=g[now][i].to;
if(g[now][i].c > 0 && cen[to] == -1)
{
cen[to] = cen[now] +1;
q.push(to);
}
}
}
return cen[n+1] != -1;
}
int dfs(int flow=inf,int now=0)
{
if(cen[now]>=cen[n+1])
{
if(now==n+1)
{
return flow;
}
else
{
return 0;
}
}
int temp,sum=0;
int to;
for(int i=0;i<g[now].size();i++)
{
to = g[now][i].to;
if(g[now][i].c>0 && flow>sum && cen[to]==cen[now]+1 )
if(temp = dfs(min(flow-sum,g[now][i].c),to))
{
sum += temp;
g[now][i].c -= temp;
g[to][g[now][i].id].c += temp;
}
}
if(!sum) cen[now] = -1;
return sum;
}
int dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs();
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&s,&t);
zx.c=s;
zx.from=0;
zx.to=i;
zx.id=g[i].size();
g[0].push_back(zx);
swap(zx.from,zx.to);
zx.id=g[0].size()-1;
zx.c=0;
g[i].push_back(zx);
zx.c=t;
zx.from=i;
zx.to=n+1;
zx.id=g[n+1].size();
g[i].push_back(zx);
swap(zx.from,zx.to);
zx.c=0;
zx.id=g[i].size()-1;
g[n+1].push_back(zx);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&zx.from,&zx.to,&zx.c);
zx.id=g[zx.to].size();
g[zx.from].push_back(zx);
zx.id=g[zx.from].size()-1;
swap(zx.from,zx.to);
g[zx.from].push_back(zx);
}
cout<<dinic()<<endl;
return 0;
}
分享到:
相关推荐
这题是道神题,神就神在,它既能让你搞懂网络流及其优化,还给了你很大的优化空间。
关于在最小割推荐题目中的源码(包括poj,Hdu两大题库的题目)
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj2516代码最小费用最大流
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1705139
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
最短增广路算法的实现 并加上了gap优化和当前弧优化 代码为POJ3469(dual core)的源码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)