Cod sursa(job #1699285)

Utilizator cojocarugabiReality cojocarugabi Data 6 mai 2016 22:41:34
Problema Taramul Nicaieri Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("harta.in");
ofstream fo("harta.out");
# define x first
# define y second
# define ll long long
# define db long double
# define scn(x) scanf("%I64d",&x)
# define scan(x) scanf("%d",&x)
# define print(x) printf("%d ",x)
# define prnt(x) printf("%I64d ",x);
# define eol printf("\n")
int F[105][105];
int d[105];
int bfs(int n)
{
    d[0] = 0;
    for (int i = 1;i <= n;++i) d[i] = -1;
    queue < int > Q;
    Q.push(0);
    while (!Q.empty() && d[n] == -1)
    {
        int node = Q.front();
        Q.pop();
        for (int i = 0;i <= n;++i)
            if (d[i] == -1 && F[node][i])
                Q.push(i),d[i] = node;
    }
    if (d[n] == -1) return 0;
    int flow = 1e9;
    for (int vertex = n;vertex;vertex = d[vertex])
        flow = min(flow,F[d[vertex]][vertex]);
    for (int vertex = n;vertex;vertex = d[vertex])
        F[d[vertex]][vertex] -= flow,F[vertex][d[vertex]] += flow;
    return flow;
}
int main(void)
{
    int n;
    fi>>n;
    int Sum1 = 0,Sum2 = 0;
    for (int i = 1;i <= n;++i)
    {
        int a,b;
        fi>>a>>b;
        Sum1 += a;
        Sum2 += b;
        F[0][i] = a;
        F[i+n][n+n+1] = b;
    }
    assert(Sum1 == Sum2 && "FUCK YOU\n");
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= n;++j)
            if (i != j) F[i][j+n] = 1;
    int flow = 0,cnt = 0;
    while ((cnt = bfs(n+n+1)) != 0) flow += cnt;
    assert(Sum1 == flow && "FUCK YOU2\n");
    vector < pair < int , int > > ans;
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= n;++j)
            if (!F[i][j+n] && F[j+n][i]) ans.push_back({i,j});
    fo << (ans.size()) << '\n';
    for (auto it : ans) fo << it.x << ' ' << it.y << '\n';
    return 0;
}