poj 2396 Budget

有源汇上下界可行流，爆炸代码，慎入！

　　题目链接：poj 2396

　　题意：设有一个 N 行 M 列的矩阵，给出每行的和，每列的和，和对一些格子的限制，求一个可行的矩阵方案。

　　题解：建立源 S 和汇 T ，每行每列都看作一个点。源点连所有行，上下界均为此行的和，所有列连汇点，上下界均为此列的和。对于每一个点，可能读入多个限制，取其上界的最小值，下界的最大值，连接对应的行点和列点。从 T 到 S 连一条下界为 0 上界为﹢ ∞ 的边，转化为了无源汇上下界可行流问题。

　　我思故我在：这道题在一开始想的时候智障了一波，一开始一直在纠结于如何让一条流固定为一个值……没想到可以让上下界一样啊O(∩_∩)O哈哈哈~

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int s,t;
int ss,tt; 
int tot=0;
struct table{
	int to,id;
};
vector<table> ve[666];
int mina[233][233],maxa[233][233];
int rd[666],cd[666];
int f[505000];
int deep[50500];
inline int min(int a,int b)
{
	return a < b ? a : b ;
}
inline bool bfs()
{
	memset(deep,-1,sizeof(deep));
	queue<int> q;
	deep[ss]=0;
	q.push(ss);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=0;i<ve[x].size();i++)
		{
			table y=ve[x][i];
			if(deep[y.to]==-1&&f[y.id]>0)
			{
				deep[y.to]=deep[x]+1;
				q.push(y.to);
			}
		}
	}
	return deep[tt]!=-1;
}
inline int zeng(int a,int b)
{
	if(a==tt) return b;
	int r=0,t;
	for(int i=0;i<ve[a].size();i++)
	{
		table y=ve[a][i];
		if(deep[y.to]==deep[a]+1&&f[y.id]>0)
		{
			t=zeng(y.to,min(b-r,f[y.id]));
			r+=t,f[y.id]-=t,f[y.id^1]+=t;
		}
	}
	if(!r) deep[a]=-1;
	return r;
}
inline int dinic()
{
	int ans=0,now;
	while(bfs())
	{
		while(now=zeng(ss,247483647)) ans+=now;
	}
	return ans;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(mina,0,sizeof(mina));
		memset(rd,0,sizeof(rd));
		memset(cd,0,sizeof(cd));
		memset(maxa,0x3f,sizeof(maxa));
		int n,m;
		scanf("%d%d",&n,&m);
		s=0,t=n+m+1; 
		ss=n+m+2,tt=n+m+3;
		for(int i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			mina[s][i]=x;
			maxa[s][i]=x;
		}
		for(int i=1;i<=m;i++)
		{
			int x;
			scanf("%d",&x);
			mina[i+n][t]=x;
			maxa[i+n][t]=x;
		}
		int p;
		scanf("%d",&p);
		for(int i=1;i<=p;i++)
		{
			int x,y,z;
			char a;
			scanf("%d %d %c %d",&x,&y,&a,&z);
			if(a=='=')
			{
				if(x==0&&y==0)
				{
					for(int i=1;i<=n;i++)
					{
						for(int j=n+1;j<=n+m;j++)
						{
							mina[i][j]=max(mina[i][j],z);
							maxa[i][j]=min(maxa[i][j],z);
						}
					}
				}
				else if(x==0)
				{
					for(int i=1;i<=n;i++)
					{
						mina[i][y+n]=max(mina[i][y+n],z);
						maxa[i][y+n]=min(maxa[i][y+n],z);
					}
				}
				else if(y==0)
				{
					for(int i=1;i<=m;i++)
					{
						mina[x][i+n]=max(mina[x][i+n],z);
						maxa[x][i+n]=min(maxa[x][i+n],z);
					}
				}
				else
				{
					mina[x][y+n]=max(mina[x][y+n],z);
					maxa[x][y+n]=min(maxa[x][y+n],z);
				}
			}
			else if(a=='<')
			{
				if(x==0&&y==0)
				{
					for(int i=1;i<=n;i++)
					{
						for(int j=n+1;j<=n+m;j++)
						{
							maxa[i][j]=min(maxa[i][j],z-1);
						}
					}
				}
				else if(x==0)
				{
					for(int i=1;i<=n;i++)
					{
						maxa[i][y+n]=min(maxa[i][y+n],z-1);
					}
				}
				else if(y==0)
				{
					for(int i=1;i<=m;i++)
					{
						maxa[x][i+n]=min(maxa[x][i+n],z-1);
					}
				}
				else
				{
					maxa[x][y+n]=min(maxa[x][y+n],z-1);
				}
			}
			else if(a=='>')
			{
				if(x==0&&y==0)
				{
					for(int i=1;i<=n;i++)
					{
						for(int j=n+1;j<=n+m;j++)
						{
							mina[i][j]=max(mina[i][j],z+1);
						}
					}
				}
				else if(x==0)
				{
					for(int i=1;i<=n;i++)
					{
						mina[i][y+n]=max(mina[i][y+n],z+1);
					}
				}
				else if(y==0)
				{
					for(int i=1;i<=m;i++)
					{
						mina[x][i+n]=max(mina[x][i+n],z+1);
					}
				}
				else
				{
					mina[x][y+n]=max(mina[x][y+n],z+1);
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			ve[s].push_back((table){i,tot}),f[tot++]=maxa[s][i]-mina[s][i];
			ve[i].push_back((table){s,tot}),f[tot++]=0;
			cd[s]+=mina[s][i];
			rd[i]+=mina[s][i];
		}
		bool flag=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=n+1;j<=n+m;j++)
			{
				if(maxa[i][j]-mina[i][j]<0)
				{
					flag=1;break;
				}
				ve[i].push_back((table){j,tot}),f[tot++]=maxa[i][j]-mina[i][j];
				ve[j].push_back((table){i,tot}),f[tot++]=0;
				cd[i]+=mina[i][j];
				rd[j]+=mina[i][j];
			}
		}
		for(int j=n+1;j<=n+m;j++)
		{
			ve[j].push_back((table){t,tot}),f[tot++]=maxa[j][t]-mina[j][t];
			ve[t].push_back((table){j,tot}),f[tot++]=0;
			cd[j]+=mina[j][t];
			rd[t]+=mina[j][t];
		}
		ve[t].push_back((table){s,tot}),f[tot++]=247483647;
		ve[s].push_back((table){t,tot}),f[tot++]=0;
		int sum1=0,sum2=0;
		for(int i=s;i<=t;i++)
		{
			if(rd[i]<cd[i])
			{
				ve[i].push_back((table){tt,tot}),f[tot++]=cd[i]-rd[i];
				ve[tt].push_back((table){i,tot}),f[tot++]=0;
				sum1+=cd[i]-rd[i];
			}
			else if(rd[i]>cd[i])
			{
				ve[ss].push_back((table){i,tot}),f[tot++]=rd[i]-cd[i];
				ve[i].push_back((table){ss,tot}),f[tot++]=0;
				sum2+=rd[i]-cd[i];
			}
		}
		if(flag||sum1!=sum2||dinic()!=sum1)	puts("IMPOSSIBLE");
		else
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=0;j<ve[i].size();j++)
				{
					table y=ve[i][j];
					if(y.to<t&&y.to>s)
						printf("%d ",(f[y.id^1]+mina[i][y.to]));
				}
				printf("\n");
			}
		}
		tot=0;
		for(int i=s;i<=tt;i++)
			ve[i].clear();
	}
	return 0;
 }