toj 1421 最大流sap

142536a

/*
题意：有N家公司和N家银行，这N家公司只会向N家银行借贷，N家银行也只借贷给N家公司，被pol**e查账，查出
N家公司分别借贷了SR，N家银行分别借出了SC，交易额限制在100以下(这个地方没看到，悲剧WA)；求这
样的借贷是否合理，合理则输出合法交易的矩阵。
题解：最大流；
建图：加入源点，在源点和银行之间加入有向边，权值为该银行借出的金额，银行和公司之间分别加入权值为100
的有向边，每间银行都指向所有的公司，加入汇点，在所有公司和汇点之间加入有向边，权值为公司所借的金额
数，求出最大流，然后银行和公司之间的边的权值的变化即为所求解。遍历所有边一次记录到矩阵中。
*/
#include <iostream>
#include <cstring>
using namespace std;
#define EMAX 20500
#define VMAX 250
const int INF = 0xfffffff;
int head[VMAX],dis[VMAX],cur[VMAX],gap[VMAX],pre[VMAX];
int map[VMAX][VMAX];
int EN;
struct edge
{
int from,to;
int weight;
int next;
}e[EMAX];
void insert(int u,int v,int w)
{
e[EN].from = u;
e[EN].to = v;
e[EN].weight = w;
e[EN].next = head;   
head = EN++;
e[EN].weight = 0;
e[EN].from = v;
e[EN].to = u;
e[EN].next = head[v];   
head[v] = EN++;
}
int sap(int s,int t, int n)//sap模版
{
memset(dis,0,sizeof(dis));
memset(gap,0,sizeof(gap));
for(int i=0; i<=n; i++)
cur = head;
int u = pre;
pre = s;
int ret = 0;
int temp = -1;
gap[0] = n;
bool flag;
while(dis < n)
{
flag = false;
for(int &i = cur; i != -1; i = e.next)
{
int v = e.to;
if(e.weight && dis == dis[v] + 1)
{
if (temp == -1 || temp>e.weight)
temp = e.weight;
pre[v] = u;
u = v;
if(v == t)
{
ret += temp;
for(u = pre;v != s;v = u,u = pre)
{
e[cur].weight -= temp;
e[cur^1].weight += temp;
}
temp = -1;
}
flag = true;
break;
}
}
if (flag)
continue;
int mindis = n;
for(int i = head; i != -1 ; i = e.next)
{
int v = e.to;
if(e.weight && mindis > dis[v])
{
cur = i;
mindis = dis[v];
}
}
gap[dis]--;
if( gap[dis] == 0)
break;
dis = mindis+1;
gap[dis]++;
u = pre;
}
return ret;
}
int main(void)
{
int n,t,sum;
while (cin >> n)
{
sum = 0;
memset(head,-1,sizeof(head));
memset(map,0,sizeof(map));
EN = 0;
for(int i=1; i<=n; i++)
{
cin >> t;
sum += t;
insert(0,i,t);//源点连接
        }
for(int i=1; i<=n; i++)
{
cin >> t;
insert(n+i,2*n+1,t);//汇点连接
        }
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)//公司和银行连接
insert(i,n+j,100);
if (sum == sap(0,n+n+1,n+n+2))
{
cout << "YES" << endl;
for(int u=1; u<=n; u++)//遍历所有边并且记录值
            {
for(int i=head; i!=-1; i=e.next)
{
if (e.to != 0)
{
map[e.to-n] = e[i^1].weight;
}
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if (j == 1)
cout << map[j];
else
cout << " " << map[j];
}
cout << endl;
}
}
else
cout << "NO" << endl;
}
return 0;
}