Pagini recente » Cod sursa (job #1084737) | Cod sursa (job #1424315) | Cod sursa (job #51230) | Cod sursa (job #504473) | Cod sursa (job #3187262)
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
vector<int>G[NMAX+5];
int capacitate[NMAX+5][NMAX+5];
int n;long long rez=0;int poz[NMAX+5];
queue<int>q;int dist[NMAX+5];
int DFS(int nod,int cap){
if(nod==n||cap==0){return cap;}
while(poz[nod]<G[nod].size()){
int nod1=G[nod][poz[nod]];poz[nod]++;
if(capacitate[nod][nod1]>0&&dist[nod1]==dist[nod]+1){
int x=DFS(nod1,min(cap,capacitate[nod][nod1]));
if(x!=0){
capacitate[nod][nod1]-=x;
capacitate[nod1][nod]+=x;return x;
}
}
}
return 0;
}
bool F_flux(){
for(int i=1;i<=n;i++){
poz[i]=0;dist[i]=INT_MAX;
}
dist[1]=0;
q.push(1);
while(!q.empty()){
int nod=q.front();q.pop();
for(int i=0;i<G[nod].size();i++){
if(capacitate[nod][G[nod][i]]>0&&dist[G[nod][i]]>dist[nod]+1){
dist[G[nod][i]]=dist[nod]+1;
q.push(G[nod][i]);
}
}
}
if(dist[n]==INT_MAX){return 0;}
long long adun=0;
while(1){
int ceva=DFS(1,INT_MAX);
if(ceva==0){break;}adun+=ceva;
}
if(adun==0){return 0;}
rez+=adun;return 1;
}
int main()
{
ifstream fin("harta.in");
ofstream fout("harta.out");
int a,b;fin>>n;
for(int i=1;i<=n;i++){
fin>>a>>b;
capacitate[1][i+1]=a;
G[1].push_back(i+1);G[i+1].push_back(1);
capacitate[n+1+i][2*n+2]=b;
G[2*n+2].push_back(n+1+i);
G[n+1+i].push_back(2*n+2);
}
for(int i=2;i<=n+1;i++){
for(int j=n+2;j<=2*n+1;j++){
if((i-1)!=(j-n-1)){
capacitate[i][j]=1;
G[i].push_back(j);
G[j].push_back(i);
}
}
}
n=2*n+2;
while(1){
if(F_flux()==0){break;}
}
int cnt=0;n-=2;n/=2;
for(int i=2;i<=n+1;i++){
for(int j=n+2;j<=2*n+1;j++){
if((i-1)!=(j-n-1)){
if(capacitate[i][j]==0){
cnt++;
}
}
}
}
fout<<cnt<<'\n';
for(int i=2;i<=n+1;i++){
for(int j=n+2;j<=2*n+1;j++){
if((i-1)!=(j-n-1)){
if(capacitate[i][j]==0){
fout<<i-1<<" "<<j-n-1<<'\n';
}
}
}
}
return 0;
}