题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=194
当所有附加边全部满流时(即maxflow==所有du[]>0之和),有可行解。
代码:
#include <iostream> @H_403_9@
#include <algorithm> @H_403_9@
#include <set> @H_403_9@
#include <map> @H_403_9@
#include <string.h> @H_403_9@
#include <queue> @H_403_9@
#include <sstream> @H_403_9@
#include <stdio.h> @H_403_9@
#include <math.h> @H_403_9@
#include <stdlib.h> @H_403_9@
#include <string>@H_403_9@
using@H_403_9@ namespace@H_403_9@ std@H_403_9@;
const@H_403_9@ int@H_403_9@ MAXN = 1010@H_403_9@;//点数的最大值@H_403_9@
const@H_403_9@ int@H_403_9@ MAXM = 400100@H_403_9@;//边数的最大值@H_403_9@
const@H_403_9@ int@H_403_9@ INF = 0x3f3f3f3f@H_403_9@;
struct@H_403_9@ Edge
{
int@H_403_9@ to,next,cap,flow;
}edge[MAXM];//注意是MAXM@H_403_9@
int@H_403_9@ tol;
int@H_403_9@ head[MAXN];
int@H_403_9@ gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void@H_403_9@ init()
{
tol = 0@H_403_9@;
memset@H_403_9@(head,-1@H_403_9@,sizeof@H_403_9@(head));
}
//加边,单向图三个参数,双向图四个参数@H_403_9@
void@H_403_9@ addedge(int@H_403_9@ u,int@H_403_9@ v,int@H_403_9@ w,int@H_403_9@ rw = 0@H_403_9@)
{
edge[tol].to = v; edge[tol].cap = w; edge[tol].next = head[u];
edge[tol].flow = 0@H_403_9@; head[u] = tol++;
edge[tol].to = u; edge[tol].cap = rw; edge[tol].next = head[v];
edge[tol].flow = 0@H_403_9@; head[v] = tol++;
}
//输入参数:起点、终点、点的总数@H_403_9@
//点的编号没有影响,只要输入点的总数@H_403_9@
int@H_403_9@ sap(int@H_403_9@ start,int@H_403_9@ end,int@H_403_9@ N)
{
memset@H_403_9@(gap,0@H_403_9@,sizeof@H_403_9@(gap));
memset@H_403_9@(dep,sizeof@H_403_9@(dep));
memcpy@H_403_9@(cur,head,sizeof@H_403_9@(head));
int@H_403_9@ u = start;
pre[u] = -1@H_403_9@;
gap[0@H_403_9@] = N;
int@H_403_9@ ans = 0@H_403_9@;
while@H_403_9@ (dep[start] < N)
{
if@H_403_9@ (u == end)
{
int@H_403_9@ Min = INF;
for@H_403_9@ (int@H_403_9@ i = pre[u]; i != -1@H_403_9@; i = pre[edge[i ^ 1@H_403_9@].to])
if@H_403_9@ (Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
for@H_403_9@ (int@H_403_9@ i = pre[u]; i != -1@H_403_9@; i = pre[edge[i ^ 1@H_403_9@].to])
{
edge[i].flow += Min;
edge[i ^ 1@H_403_9@].flow -= Min;
}
u = start;
ans += Min;
continue@H_403_9@;
}
bool@H_403_9@ flag = false@H_403_9@;
int@H_403_9@ v;
for@H_403_9@ (int@H_403_9@ i = cur[u]; i != -1@H_403_9@; i = edge[i].next)
{
v = edge[i].to;
if@H_403_9@ (edge[i].cap - edge[i].flow && dep[v] + 1@H_403_9@ == dep[u])
{
flag = true@H_403_9@;
cur[u] = pre[v] = i;
break@H_403_9@;
}
}
if@H_403_9@ (flag)
{
u = v;
continue@H_403_9@;
}
int@H_403_9@ Min = N;
for@H_403_9@ (int@H_403_9@ i = head[u]; i != -1@H_403_9@; i = edge[i].next)
if@H_403_9@ (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
{
Min = dep[edge[i].to];
cur[u] = i;
}
gap[dep[u]]--;
if@H_403_9@ (!gap[dep[u]])return@H_403_9@ ans;
dep[u] = Min + 1@H_403_9@;
gap[dep[u]]++;
if@H_403_9@ (u != start) u = edge[pre[u] ^ 1@H_403_9@].to;
}
return@H_403_9@ ans;
}
int@H_403_9@ n,m;
int@H_403_9@ in[MAXN],least[MAXM],num[MAXM];
int@H_403_9@ main()
{
while@H_403_9@ (~scanf@H_403_9@("%d%d"@H_403_9@,&n,&m))
{
init();
memset@H_403_9@(in,sizeof@H_403_9@(in));
memset@H_403_9@(least,sizeof@H_403_9@(least));
int@H_403_9@ a,b,c,d;
for@H_403_9@ (int@H_403_9@ i = 1@H_403_9@;i <= m;i++)
{
scanf@H_403_9@("%d%d%d%d"@H_403_9@,&a,&b,&c,&d);
num[i] = tol;
least[i] = c;
in[a] -= c;
in[b] += c;
addedge(a,d - c);
}
int@H_403_9@ sum = 0@H_403_9@;
for@H_403_9@ (int@H_403_9@ i = 1@H_403_9@;i <= n;i++)
{
if@H_403_9@ (in[i] > 0@H_403_9@)
{
addedge(0@H_403_9@,i,in[i]);
sum += in[i];
}
else@H_403_9@ addedge(i,n + 1@H_403_9@,-in[i]);
}
if@H_403_9@ (sap(0@H_403_9@,n + 2@H_403_9@) != sum) puts@H_403_9@("NO"@H_403_9@);
else@H_403_9@
{
puts@H_403_9@("YES"@H_403_9@);
for@H_403_9@ (int@H_403_9@ i = 1@H_403_9@;i <= m;i++) printf@H_403_9@("%d\n"@H_403_9@,edge[num[i]].flow + least[i]);
}
}
return@H_403_9@ 0@H_403_9@;
}