POJ2396 Budget 有源上下界可行流

有源上下界可行流的做法就是无源可行流的虚拟终点t连接一条通往虚拟重点s的一个容量为inf的边就好了。。。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 5e2, maxm = 5e4+10,inf=0x3f3f3f3f;

int head[maxn],tot;
struct Edge{int to,f,nxt;}e[maxm];
void add(int from,int to,int f)
{
	e[tot].nxt = head[from],e[tot].to = to, e[tot].f = f,head[from]=tot++;
	e[tot].nxt = head[to],e[tot].to = from,e[tot].f = 0,head[to] = tot++;
}
int tre[maxn],up[maxn][maxn],low[maxn][maxn];
void init(int n,int m)
{
	memset(head,-1,sizeof(head)); tot = 0;
	memset(tre,0,sizeof(tre));
	for(int i = 0; i <= n; ++i)
	for(int j = 0; j <= m; ++j)
	up[i][j] = inf, low[i][j] = 0;
}
bool buil(int n,int m)
{
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j)
	if(low[i][j] > up[i][j]) return 0;
	else
	{
		tre[i]-=low[i][j],tre[j+n]+=low[i][j];
		add(i,j+n,up[i][j]-low[i][j]);
	}
	return 1;
}
int dep[maxn];
bool bfs(int s,int t)
{
	memset(dep,0,sizeof(dep));
	queue<int> q; q.push(s); dep[s] = 1;
	while(!q.empty())
	{
		int fa = q.front(); q.pop();
		for(int i = head[fa]; ~i; i = e[i].nxt)
		{
			int to = e[i].to, f = e[i].f;
			if(f && !dep[to])
			{
				dep[to] = dep[fa]+1;
				q.push(to);
			}
		}
	}
	return dep[t];
}
int dfs(int s,int t,int flow)
{
	if(s == t) return flow;
	int ss = 0;
	for(int i = head[s]; ~i; i = e[i].nxt)
	{
		int to = e[i].to, f = e[i].f;
		if(f && dep[to] == dep[s]+1)
		{
			int ans = dfs(to,t,min(flow,f));
			flow-=ans; ss+=ans;
			e[i].f -= ans; e[i^1].f+=ans;
		}
	}
	if(ss == 0) dep[s] = 0;
	return ss;
}
void dinic(int s,int t)
{
	long long ans = 0;
	while(bfs(s,t)) dfs(s,t,0x3f3f3f3f);
	
}
void limitflow(int s,int t,int n,int m)
{
	int x = t + 1, y = t + 2;
	for(int i = 0; i <= t; ++i)
	{
		if(tre[i] > 0) add(x,i,tre[i]);
		else if(tre[i] < 0) add(i,y,-tre[i]);
		
	}
	add(t,s,inf);
	dinic(x,y);
	for(int i = head[x]; i; i = e[i].nxt)
	{
		if(e[i].f)
		{
			printf("IMPOSSIBLE\n\n");
			return;
		}
	}
	int j;
	for(int i = 1; i <= n; ++i)
	{
		for(j = 1; j < m; ++j)
		printf("%d ",e[((i-1)*m+j)*2-1].f+low[i][j]);
		printf("%d\n",e[i*m*2-1].f+low[i][j]);
	}
	printf("\n");
}
int main()
{
	int cas,cas1,n,m,s,t,u,v,sum1,sum2,d,f1,t1,f2,t2;
	char c[2];
	scanf("%d",&cas);
	for(int tt = 1; tt <= cas; ++tt)
	{
		sum1 = 0; sum2 = 0;
		scanf("%d%d",&n,&m);
		s = 0, t = n + m + 1;
		init(n,m);
		for(int i = 1; i <= n; ++i)
		scanf("%d",&u),tre[s]-=u,tre[i]+=u,sum1+=u;
		for(int i = n+1; i <= n+m; ++i)
		scanf("%d",&u),tre[i]-=u,tre[t]+=u,sum2+=u;
		scanf("%d",&cas1);
		while(cas1--)
		{
			scanf("%d%d%s%d",&u,&v,c,&d);
			f1 = t1 = u, f2 = t2 = v;
			if(u==0) f1 = 1,t1 = n;
			if(v==0) f2 = 1,t2 = m;
			for(int i = f1; i <= t1; ++i)
			for(int j = f2; j <= t2; ++j)
			if(c[0]=='=')
			low[i][j]=max(d,low[i][j]),up[i][j]=min(d,up[i][j]);
			else if(c[0]=='>')
			low[i][j] = max(d+1,low[i][j]);
			else 
			up[i][j] = min(d-1,up[i][j]);
		}
		
		if(sum1==sum2&&buil(n,m)) limitflow(s,t,n,m);
		else printf("IMPOSSIBLE\n\n");
	}
}