Pagini recente » Cod sursa (job #2441499) | Cod sursa (job #2554981) | Cod sursa (job #2092323) | Cod sursa (job #3250423) | Cod sursa (job #3196378)
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
using pii = pair<int,int>;
const int inf = 1e9;
struct edge
{
int y , cap , flow , ridx;
};
vector <edge> g[202];
int source , sync , n , a , b , sz[202], level[202] , ef[202];
queue<int>q;
bool bfs()
{
memset(level,0,sizeof(level));
memset(ef,0,sizeof(ef));
q.push(source);
level[source] = 1;
while(!q.empty())
{
a = q.front(); q.pop();
for(auto it : g[a])
{
if(!level[it.y] && it.cap > it.flow)
{
level[it.y] = level[a]+1;
q.push(it.y);
}
}
}
return(level[sync]>0);
}
int aug(int x , int flow)
{
if(x == sync) return flow;
for(; ef[x] < sz[x] ; ef[x]++)
{
edge it = g[x][ef[x]];
if(level[it.y]==level[x]+1 && it.cap>it.flow)
{
int nf = aug(it.y,min(flow,it.cap-it.flow));
if(!nf) continue;
g[x][ef[x]].flow += nf;
g[it.y][g[x][ef[x]].ridx].flow -= nf;
return nf;
}
}
return 0;
}
int main()
{
cin >> n;
source = 0;
sync = n+n+1;
for(int i = 1 ; i <= n ; ++i)
{
cin >> a >> b;
g[0].push_back({i,a,0,sz[i]++});
g[i].push_back({0,0,0,sz[0]++});
g[n+i].push_back({sync,b,0,sz[sync]++});
g[sync].push_back({n+i,0,0,sz[n+i]++});
for(int j = 1 ; j <= n ; ++j)
{
if(j == i) continue;
g[i].push_back({j+n,1,0,sz[j+n]++});
g[j+n].push_back({i,0,0,sz[i]++});
}
}
while(bfs())
{
while(true)
{
if(!aug(source,inf)) break;
}
}
vector<pii>ans;
for(int i = 1 ; i <= n ; ++i)
{
for(auto it : g[i])
{
if(!it.cap || it.cap-it.flow>0) continue;
ans.push_back({i,it.y-n});
}
}
cout << ans.size() << '\n';
for(auto it : ans)
{
cout << it.first << ' ' << it.second << '\n';
}
return 0;
}