Pagini recente » Cod sursa (job #1652285) | Cod sursa (job #1122585) | Cod sursa (job #886590) | Cod sursa (job #1195976) | Cod sursa (job #984667)
Cod sursa(job #984667)
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define pb push_back
#define NODES 220
#define inf 0x3f3f3f3f
using namespace std;
int n, source, sink, capacity[NODES][NODES], f[NODES][NODES], p[NODES], edges;
bool visited[NODES];
queue <int> q;
vector <int> adj[NODES];
inline void read()
{
freopen("harta.in", "r", stdin);
int x, y;
scanf("%d", &n);
source=2*n+1; sink=2*n+2;
for(int i=1;i<=n;++i)
{
scanf("%d %d", &x, &y);
edges+=x;
adj[source].pb(i); adj[i].pb(source); capacity[source][i]=x;
adj[i+n].pb(sink); adj[sink].pb(i+n); capacity[i+n][sink]=y;
for(int j=1;j<=n;++j)
if(i!=j)
{
adj[i].pb(j+n); adj[j+n].pb(i);
capacity[i][j+n]=1;
}
}
}
inline void write()
{
freopen("harta.out", "w", stdout);
printf("%d\n", edges);
for(int i=1;i<=n;++i)
for(int j=n+1;j<=2*n;++j)
if(f[i][j])
printf("%d %d\n", i, j-n);
}
inline bool BFS()
{
memset(visited, 0, sizeof(visited));
q.push(source); visited[source]=1;
while(!q.empty())
{
int node=q.front(); q.pop();
if(node==sink)
continue;
for(vector <int> :: iterator it=adj[node].begin(); it!=adj[node].end(); ++it)
if(!visited[*it] && capacity[node][*it] > f[node][*it])
{
visited[*it]=1;
p[*it]=node;
q.push(*it);
}
}
return visited[sink];
}
inline void solve()
{
int min_flow, node;
while(BFS())
for(vector <int> :: iterator it=adj[sink].begin(); it!=adj[sink].end(); ++it)
{
p[sink]=*it;
min_flow=inf;
for(int i=sink; i!=source; i=p[i])
min_flow=min(min_flow, capacity[p[i]][i]-f[p[i]][i]);
for(int i=sink; i!=source; i=p[i])
{
f[p[i]][i]+=min_flow;
f[i][p[i]]-=min_flow;
}
}
}
int main()
{
read();
solve();
write();
return 0;
}