请不要随便指点别人该怎么做、每一个人的人生都应该自己掌握、你给不了别人一切、你也不懂别人的忧伤、
微笑不代表快乐、哭泣不一定悲伤
不努力怎么让关心你的人幸福、不努力怎么让看不起你的人绝望、
我用生命在奋斗——lx_Zz
—————————————————————————————————————————————————————————————
————————————————————————— 华丽的切割线 ————————————————————————————
—————————————————————————————————————————————————————————————
敬仰完《最小割模型在信息学中的应用》论文之后切一下例题、发现自己太弱了。。
。
。orz
/* 题目： vijos 1352 *//* 作者： lx_Zz *//* 时间： 2014.5.20 */#include非递归更高效的#include #include #include using namespace std;#define N 60005#define INF 0x7fffffffint 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