1421. Credit Operations
3305 단어 Opera
네트워크 흐름 겨우
코드:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int M=205,N=105;
const int INF=0x3f3f3f3f;
//typedef pair<int,int>point;
int deal[N][N],L[M];
struct node
{
int j,next;
int flow;
}side[M*M];
int head[M],I;
int n,sum,nd;
void add(int i,int j,int flow)
{
side[I].j=j;
side[I].flow=flow;
side[I].next=head[i];
head[i]=I++;
}
bool bfs(int x1,int x2)
{
memset(L,-1,sizeof(L));
queue<int>qt;
qt.push(x1);
L[x1]=0;
while(!qt.empty())
{
int x=qt.front();
qt.pop();
for(int t=head[x];t!=-1;t=side[t].next)
{
int j=side[t].j;
if(side[t^1].flow>0&&L[j]==-1)
{
L[j]=L[x]+1;
qt.push(j);
}
}
}
if(L[x2]==-1)
return false;
return true;
}
int dfs(int x,int sum)
{
if(x==nd)
return sum;
int tmp=sum;
for(int t=head[x];t!=-1;t=side[t].next)
{
int j=side[t].j;
if(side[t].flow>0&&L[x]==L[j]+1)
{
int w=dfs(j,min(tmp,side[t].flow));
side[t].flow-=w;
side[t^1].flow+=w;
if(x>=1&&x<=n&&j>=n+1&&j<=2*n)
{
deal[x][j-n]+=w;
}
if(j>=1&&j<=n&&x>=n+1&&x<=2*n)
{
deal[j][x-n]-=w;
}
tmp-=w;
if(tmp==0)
break;
}
}
return (sum-tmp);
}
int main()
{
while(cin>>n)
{
memset(head,-1,sizeof(head));
I=0;
nd=n*2+1;
int A=0,B=0;
for(int i=1;i<=n;++i)
{
int a;
cin>>a;
A+=a;
add(0,i,a);
add(i,0,0);
}
for(int i=1;i<=n;++i)
{
int b;
cin>>b;
B+=b;
add(i+n,nd,b);
add(nd,i+n,0);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{add(i,j+n,100);add(j+n,i,0);}
int ans=0;
while(bfs(nd,0))
{
int k;
while((k=dfs(0,INF)))
ans+=k;
}
//cout<<ans<<endl;
if(A!=B||A!=ans)
cout<<"NO"<<endl;
else
{
cout<<"YES"<<endl;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
cout<<deal[i][j]<<" ";
}
cout<<endl;
}
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
클립보드로 컨텐트 복사//txt参数为显示和复制的文本内容 function copyToBoard(txt) { if(window.clipboardData) { window.clipboardData.clearData(); window.clipb...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.