请不要随便指点别人该怎么做、每个人的人生都应该自己掌握、你给不了别人一切、你也不懂别人的忧伤、
微笑不代表快乐、哭泣不一定悲伤
不努力怎么让关心你的人幸福、不努力怎么让看不起你的人绝望、
我用生命在奋斗――lx_Zz
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――
――――――――――――――――――――――――― 华丽的分割线 ――――――――――――――――――――――――――――
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――
仰慕完《最小割模型在信息学中的应用》论文之后切一下例题、发现自己太弱了。。。。orz
/* 题目： vijos 1352 */ /* 作者： lx_Zz */ /* 时间： 2014.5.20 */ #include#include #include #include using namespace std; #define N 60005 #define INF 0x7fffffff int n,m,k; int level[N]; struct node { int to,next,cost; }edge[500005]; int num[N]; int head[N]; int t_head[N]; int start,end; void init() { k=0; memset(head,-1,sizeof(head)); } int bfs(int s,int t)//对顶点进行标号、找出层次图 { memset(level,0,sizeof(level)); queue q; q.push(s); level[s]=1; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=edge[i].next) { int y=edge[i].to; if(!level[y]&&edge[i].cost>0) { level[y]=level[now]+1; q.push(y); } } } return level[t]!=0;//汇点是否在层次图中 } int dfs(int s,int cp)//在层次图中寻找增广路进行增广 { int flow=0,temp; int t; if(s==end||cp==0)return cp; for(;t_head[s]+1;t_head[s]=edge[t_head[s]].next) { int y=edge[t_head[s]].to; if(level[s]+1==level[y]) { temp=dfs(y,min(cp,edge[t_head[s]].cost)); if(temp>0) { edge[t_head[s]].cost-=temp; edge[t_head[s]^1].cost+=temp; flow+=temp; cp-=temp; if(cp==0)break; } } } return flow; } int dinic() { int ans=0,flow=0; while(bfs(start,end))//汇点不在层次图中、算法终止 { for(int i=0;i<=end;i++) t_head[i]=head[i]; ans+=dfs(start,INF); } return ans; } void add(int x,int y,int val) { edge[k].to=y; edge[k].cost=val; edge[k].next=head[x]; head[x]=k++; edge[k].to=x; edge[k].cost=0; edge[k].next=head[y]; head[y]=k++; } int main() { //freopen("C:\\Users\\终将我要华丽的逆袭\\Desktop\\lx_Zz_in.txt","r",stdin); //freopen("C:\\Users\\终将我要华丽的逆袭\\Desktop\\lx_Zz_out.txt","w",stdout); int n,m; scanf("%d%d",&n,&m); init(); int x; start=0;end=n+m+1; for(int i=1;i<=n;i++) { scanf("%d",&x); add(start,i,x); } int sum=0; for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,n+i,INF); add(b,n+i,INF); add(n+i,end,c); sum+=c; } int ans=dinic(); printf("%d\n",sum-ans); return 0; }
非递归更高效的
/* 题目： vijos 1352 */ /* 作者： lx_Zz */ /* 时间： 2014.5.20 */ #include#include #include #include