Pagini recente » Cod sursa (job #1856870) | Cod sursa (job #1076805) | Cod sursa (job #1830967) | Cod sursa (job #1776426) | Cod sursa (job #3321439)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,x,y,source,sink, flow[500][500],cap[500][500],dist[500];
vector <int> edges[500];
queue <int> q;
void add_edge(int x, int y, int c){
edges[x].push_back(y);
edges[y].push_back(x);
cap[x][y]+=c;
}
bool bfs(int source, int destination){
for(int i=source; i<=destination; i++)
dist[i] = INT_MAX;
dist[source] = 0;
q.push(source);
while(!q.empty())
{
int x=q.front();
q.pop();
for(auto y:edges[x])
if(dist[y] > dist[x]+1 and flow[x][y] < cap[x][y])
dist[y] = dist[x]+1, q.push(y);
}
return dist[destination]!=INT_MAX;
}
int maxflow(int x, int sink, int maximumflow){
if(x == sink)
return maximumflow;
if(maximumflow == 0)
return 0;
int totalflow = 0;
for(auto y:edges[x])
if(dist[y] == dist[x]+1)
{
int currentflow = maxflow(y, sink, min(maximumflow - totalflow, cap[x][y] - flow[x][y]));
flow[x][y] += currentflow;
flow[y][x] -= currentflow;
totalflow += currentflow;
}
return totalflow;
}
int main()
{
f>>n;
source = 0, sink = n+n+1;
for(int i=1; i<=n; i++)
{
f>>x>>y;
add_edge(source, i, x);
add_edge(n+i, sink, y);
for(int j=1; j<=n; j++)
if(i!=j)
add_edge(i, n+j, 1);
}
int totalflow=0;
while(bfs(source, sink))
totalflow += maxflow(source, sink, INT_MAX);
g<<totalflow<<'\n';
for(int i=1; i<=n; i++)
for(int j=n+1; j<=n+n; j++)
if(flow[i][j]==1)
g<<i<<' '<<j-n<<'\n';
return 0;
}