思路
题目给出了每个点的初度和入度，由于图是无重边无自环的有向图。
要求满足限制的图有多少条边与建图方案。
我们可以考虑使用网络流中的最大流。
我们知道这是一道网络流后，题目的难点就转移到网络流的建模以及输出方案的办法。
网络流的建模：
题目所给的条件没有源点汇点并指出图可以不连通，所以考虑设立一个超级源点 \(S\) 以及汇点 \(T\)。
由于有入度和初度的要求，图是有向图。
考虑拆点。
将每一个点拆成两个点，一个代表由其他点连向自己，即入度。
反之同理，另一个点代表自己连向其他点，即出度。
针对由有些边不能连，由于本题数据较小，我们可以使用一个邻接矩阵来存该边可不可以连。
注意：没有自环，所以自己不能连自己。
所以综上所述，本题的建模规则：
1：每个点的入度连向汇点，流量为入度 \(a _ {i}\)。
2：源点连向每个点的出度，流量为出度 \(b _ {i}\)。
3：可以连的边，起点的出度点连向终点的入读点，流量为 1（没有重边）。
保证有解，所以建模规则 1 和 2 中的连的边满流。
然后就可以跑一遍最大流 Dinic 板子。
输出方案：
连的边必然是建模规则 3 中连的边，当该边被选中时必然满流（因为流量只有 1）。
但这种边一定是由出度点连向入读点。
下面给出代码：
代码
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf 1e9
using namespace std;
int n,m,s,t;
int mapp[1005][1005];
int cnt=-1;
struct N{
int from,to,next,val;
};N p[10000005];
int head[8005],cur[8005],d[8005];
inline void add(int a,int b,int c)
{
++cnt;
p[cnt].from=a;
p[cnt].next=head[a];
head[a]=cnt;
p[cnt].to=b;
p[cnt].val=c;
return ;
}
inline int bfs()
{
queue<int> q;
q.push(s);
memset(d,-1,sizeof(d));
d[s]=0;
while(q.size()>0)
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=p[i].next)
{
int v=p[i].to;
if(d[v]==-1&&p[i].val>0)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
if(d[t]==-1) return 0;
else return 1;
}
inline int dfs(int u,int limit)
{
if(u==t||!limit) return limit;
int sum=0,flow=0;
for(int i=cur[u];i!=-1;i=p[i].next)
{
int v=p[i].to;
cur[u]=i;
if(d[v]==d[u]+1&&p[i].val>0)
{
sum=dfs(v,min(p[i].val,limit));
p[i].val-=sum;
p[i^1].val+=sum;
flow+=sum;
limit-=sum;
if(!limit) break;
}
}
if(!flow) d[u]=-1;
return flow;
}
inline void dinic()
{
int ans=0;
while(bfs())
{
for(int i=0;i<=t;i++) cur[i]=head[i];
ans+=dfs(s,inf);
}
cout<<ans<<endl;
return ;
}//板子
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
memset(head,-1,sizeof(head));//s=0,memset head数组为-1
cin>>n;
s=0,t=2*n+1;
int a,b;
for(int i=1;i<=n;i++)
{
cin>>a;
add(i+n,t,a),add(t,i+n,0);//建模规则1
}
for(int i=1;i<=n;i++)
{
cin>>a;
add(s,i,a),add(i,s,0);//建模规则2
}
//拆点：这里我们将出度点的编号设为1-n,入度点就是n+1-2*n,所以汇点t可设为2*n+1
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
mapp[a][b]=1;//邻接矩阵
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mapp[i][j]==0&&i!=j)//当此边没有被限制且不是自己连向自己时
{
add(i,n+j,1),add(n+j,i,0);//连边
}
}
}
dinic();
for(int i=4*n-1;i<=cnt;i++)//建图规则3中连的边cnt值从4*n-1到cnt
{
if(i%2==0&&p[i].val==0)//是从出度连向入度的边且满流了(val值为0)
{
cout<<p[i].from<<" "<<p[i].to-n<<endl;//输出时入度点要记得减去n
}
}
return 0;
}