Mai intai trebuie sa te autentifici.
Cod sursa(job #1963548)
Utilizator | Data | 12 aprilie 2017 16:55:14 | |
---|---|---|---|
Problema | Taramul Nicaieri | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.09 kb |
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge
{
int x,y,cap,flow,inv;
};
vector<edge> muc;
vector<int> v[210];
queue<int> q;
int out[110],in[110],vaz[210],n,tata[210];
void add_edge(int x,int y,int cap)
{
int a=muc.size();
muc.push_back({x,y,cap,0,a+1});
muc.push_back({y,x,0,0,a});
v[x].push_back(a);
v[y].push_back(a+1);
}
int bfs(int S,int D)
{
for(int i=0;i<=2*n+1;i++) vaz[i]=0;
q.push(S);
vaz[S]=1;
while(!q.empty())
{
int nod=q.front();
q.pop();
for(int i=0;i<v[nod].size();i++)
{
int a=v[nod][i];
int vec=muc[a].y;
if(vaz[vec]==0 && muc[a].flow<muc[a].cap)
{
vaz[vec]=1;
if(vec!=D) q.push(vec);
tata[vec]=a;
}
}
}
return vaz[D];
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
int flux=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&out[i],&in[i]);
int S=0,D=2*n+1;
for(int i=1;i<=n;i++) add_edge(S,i,out[i]);
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(i!=j-n) add_edge(i,j,1);
for(int i=n+1;i<=2*n;i++)
add_edge(i,D,in[i-n]);
while(bfs(S,D))
{
for(int i=0;i<v[D].size();i++)
{
int a=muc[v[D][i]].inv;
if(vaz[muc[a].x]==0 or muc[a].flow==muc[a].cap) continue;
tata[D]=a;
int s=1e9;
for(int nod=D;nod!=S;nod=muc[tata[nod]].x) s=min(s,muc[tata[nod]].cap-muc[tata[nod]].flow);
for(int nod=D;nod!=S;nod=muc[tata[nod]].x)
{
muc[tata[nod]].flow+=s;
muc[muc[tata[nod]].inv].flow-=s;
}
flux+=s;
}
}
printf("%d\n",flux);
for(int i=0;i<muc.size();i++)
if(muc[i].flow==1 && muc[i].x>=1 && muc[i].x<=n && muc[i].y>=n+1 && muc[i].y<=2*n) printf("%d %d\n",muc[i].x,muc[i].y-n);
return 0;
}