[Gym-102006G] [Problem G] Is Topo Logical?

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Maxn = 2e5+10;
const int Inf = 0x7f7f7f7f;
const int Mod = 1e9+7;

bool flag;
int n,tol,tol1,tol2,tolans,Sum1,Sum2;
int in1[Maxn],in2[Maxn],in3[Maxn];

vector<int> v;
pii p[Maxn],p1[Maxn],p2[Maxn],ans[Maxn];

void get_map1(){
    for(int i=1;i<=tol;i++)
    {
        int cnt = 0;
        for(int j=1;j<=tol&&cnt<p[i].first;j++)
            if( i != j )
            {
                cnt++;
                ans[++tolans] = make_pair(p[j].second,p[i].second);
            }
        if( cnt != p[i].first )  flag = false;
    }
}
void get_map2(){
    for(int i=1;i<=tol;i++)
    {
        int cnt = 0;
        for(int j=1;j<=tol1&&cnt<in3[p[i].second];j++)
        {
            cnt++;
            ans[++tolans] = make_pair(p1[j].second,p[i].second);
        }
        if( cnt != in3[p[i].second] )  flag = false;
        in3[p[i].second] = 0;
    }
}
void get_map3(){
    sort(p2+1,p2+1+tol2);
    for(int i=1;i<=tol2;i++)
    {
        int Size = v.size(), cnt = 0;
        for(int j=0;j<Size&&cnt<p2[i].first;j++)
        {
            cnt++;
            ans[++tolans] = make_pair(v[j],p2[i].second);
        }
        if( cnt != p2[i].first )  flag = false;
        v.push_back(p2[i].second);
    }
}

void Out(){
    printf("%d\n",tolans);
    for(int i=1;i<=tolans;i++)
        printf("%d %d\n",ans[i].first,ans[i].second);
}

int main(){
    freopen("topo.in","r",stdin);
    int T;
    scanf("%d",&T);
    while( T-- )
    {
        scanf("%d",&n);
        v.clear();
        Sum1 = Sum2 = tol = tol1 = tol2 = tolans = 0;
        flag = true;
        for(int i=1;i<=n;i++)  
        {
            scanf("%d",in1+i), Sum1 += in1[i];
            if( in1[i] == 0 )  v.push_back(i);
            if( in1[i] >= n )  flag = false;
        }
        for(int i=1;i<=n;i++)  
        {
            scanf("%d",in2+i), Sum2 += in2[i];
            if( in2[i] != 0 )  p[++tol] = make_pair(in2[i],i);
            if( in2[i] == 0 )  p1[++tol1] = make_pair(0,i);
            in3[i] = in1[i] - in2[i];
            if( in1[i] != 0 && in2[i] == 0 )  p2[++tol2] = make_pair(in1[i],i);
            if( in2[i] > in1[i] )  flag = false;
        }
        if( Sum2 == 1 || !flag )  {puts("-1");continue;}
        get_map1();
        get_map2();
        get_map3();
        if( !flag || Sum1 != tolans )  puts("-1");
        else Out();
    }
    return 0;
}

[Gym-102006G] [Problem G] Is Topo Logical?

原文：https://www.cnblogs.com/HexQwQ/p/13363493.html