Pagini recente » Cod sursa (job #2973975) | Cod sursa (job #3148516) | Cod sursa (job #1392898) | Cod sursa (job #365481) | Cod sursa (job #2513562)
#include <iostream>
#include <list>
#include <cstring>
#include <unordered_map>
#include <numeric>
#include <cassert>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef long double LD;
const int inf = 2*(1e9);
const long long infl = 2*(1e18) + 10;
const long long MOD = 998244853;
const int NMAX = 500;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
int C[NMAX][NMAX];
int F[NMAX][NMAX];
vector<int> G[NMAX];
int p[NMAX];
bool viz[NMAX];
int N,M,flow,x,y,z,minf;
queue<int> q;
bool bfs()
{
q.push(1);
memset(viz, 0, sizeof(viz));
viz[1]=1;
while(!q.empty())
{
int curr=q.front(); q.pop();
if(curr==N)
continue;
for(int i=0; i<G[curr].size(); ++i)
{
int v=G[curr][i];
if(C[curr][v] == F[curr][v] || viz[v])
continue;
viz[v]=true;
q.push(v);
p[v]=curr;
}
}
return viz[N];
}
int outdegree[NMAX];
int indegree[NMAX];
void solve()
{
int n;
cin>>n;
for(int i = 1; i <= n; ++i){
cin>>outdegree[i]>>indegree[i];
}
N = 2*n + 2;
for(int i = 1; i <= n; ++i){
C[1][1 + i] = outdegree[i];
G[1].push_back(1 + i);
G[1 + i].push_back(1);
C[1 + i + n][N] = indegree[i];
G[1 + i + n].push_back(N);
G[N].push_back(1 + i + n);
}
for(int i = 1; i <= n; ++i){
for(int j = i+1; j <= n; ++j){
C[1 + i][1 + j + n] = 1;
G[1 + i].push_back(1 + j + n);
G[1 + j + n].push_back(1 + i);
C[1 + j][1 + i + n] = 1;
G[1 + j].push_back(1 + i + n);
G[1 + i + n].push_back(1 + j);
}
}
flow = 0;
bfs();
while(bfs())
{
for(int i=0; i < G[N].size(); ++i)
{
int curr = G[N][i];
if(C[curr][N] == F[curr][N] || !viz[curr])
continue;
minf = 0xffffff;
p[N]=curr;
for(int i=N; i!=1; i=p[i])
minf=min(minf, C[p[i]][i]-F[p[i]][i]);
if(minf==0)
continue;
for(int i=N; i!=1; i=p[i])
{
F[p[i]][i]+=minf;
F[i][p[i]]-=minf;
}
flow+=minf;
}
}
vector<pair<int, int>> edges;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i != j){
if(F[1 + i][1 + j + n] == 1){
edges.push_back({i, j});
}
}
}
}
cout<<edges.size()<<"\n";
for(auto p: edges){
cout<<p.first<<" "<<p.second<<"\n";
}
//cout<<flow<<"\n";
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cout << setprecision(16) << fixed;
assert(freopen("harta.in", "rt", stdin));
assert(freopen("harta.out", "wt", stdout));
solve();
return 0;
}