Pagini recente » Cod sursa (job #2470613) | Cod sursa (job #1188636) | Cod sursa (job #1117424) | Cod sursa (job #1550460) | Cod sursa (job #331982)
Cod sursa(job #331982)
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int maxn=220;
const int INF=0x3f3f3f3f;
queue<int>Q;
vector<int>a[maxn];
int F[maxn][maxn],C[maxn][maxn],i,j,n,m,x,gradei[maxn],gradeo[maxn];
int val[maxn],source,dest;
int bfs()
{
int x;
memset(val,0,sizeof(val));
Q.push(source);
val[source]=INF;
while(!Q.empty())
{
x=Q.front();
Q.pop();
if(x==dest)
continue;
for(vector<int>::iterator it=a[x].begin();it!=a[x].end();++it)
if(val[*it]==0&&F[x][*it]!=C[x][*it])
val[*it]=x,Q.push(*it);
}
return val[dest];
}
int main()
{
f>>n;
source=2*n+2;;
dest=2*n+1;
for(i=1;i<=n;++i)
{
f>>gradei[i];
f>>gradeo[i];
a[source].push_back(i);
a[i].push_back(source);
C[source][i]=gradei[i];
a[i+n].push_back(dest);
a[dest].push_back(i+n);
C[i+n][dest]=gradeo[i];
}
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
{
a[i].push_back(j+n);
a[j+n].push_back(i);
C[i][j+n]=1;
a[j].push_back(i+n);
a[i+n].push_back(j);
C[j][i+n]=1;
}
int flow,fmin;
for(flow=0;bfs();)
for(vector<int>::iterator it=a[dest].begin();it!=a[dest].end();++it)
{
x=*it;
if(val[x]==0||F[x][dest]==C[x][dest])
continue;
fmin=INF;
val[dest]=x;
for(i=dest;i!=source;i=val[i])
fmin=min(fmin,C[val[i]][i]-F[val[i]][i]);
if(fmin==0)
continue;
for(i=dest;i!=source;i=val[i])
F[val[i]][i]+=fmin,F[i][val[i]]-=fmin;
flow+=fmin;
}
g<<flow<<"\n";
for(i=1;i<=n;++i)
for(j=n+1;j<=n*2;++j)
if(F[i][j]==1)
g<<i<<" "<<j-n<<"\n";
f.close();
g.close();
return 0;
}