题目链接：
大致题意：
给出一个有向图D=(V,E).对于每个点U，定义两种操作a(u),b(u)
操作a(u)：删除点U的所有出边，即属于E，操作花费为Ca(u).
操作b(u)：删除点U的所有入边，即属于E，操作花费为Cb(u).
求将原图的边集的边全部删除的最小代价，总操作数和具体操作
Solution:
第一问很简单，首先，对于每一个点，把它分成出点和入点。
把每个点的出点与S相连，入点与T相连。边容量分别为删除该点所有入边和出边的花费。
然后对于每条边 a -> b，就把a的出点与b的入点连一条容量为inf的边。
根据最大流=最小割，跑一遍dinic就能得到答案了。
对于第二、三问，我们分别统计a操作和b操作。
我们先对剩余网络进行bfs()，把能够扫到的点都标记为1，不能的标记为0。
对于一个点u，如果要使用a(u)，那么显然，需要至少存在一个点v，满足u -> v &&
vis[u]==vis[v]==0。而对于点u，如果要使用b(u)，只需要满足vis[u]==1就行了。
为了防止重复输出，在定义一个apr数组记录每个数是否加入到答案中就行了。
详见代码
Code:
#include#include #include #include #include #define N 1001#define M 20001#define inf 1926081700using namespace std;int S,T,head[N];int n,m,cnt=1;int ru[N],cu[N];int ans,vis[N],apr[N];int t1,t2,fst[N],sec[N];struct Edge{int nxt,to,val;}edge[M];void ins(int x,int y,int z){ edge[++cnt].nxt=head[x]; edge[cnt].to=y;edge[cnt].val=z; head[x]=cnt;}namespace Network_Flow{ queue q; int dep[N]; int bfs(){ memset(dep,0,sizeof(dep)); q.push(S);dep[S]=1; while(!q.empty()){ int x=q.front();q.pop(); for(int i=head[x];i;i=edge[i].nxt){ int y=edge[i].to,v=edge[i].val; if(!dep[y]&&v){ q.push(y); dep[y]=dep[x]+1; } } } return dep[T]; } int dfs(int x,int rest){ if(x==T||rest<=0) return rest; int flow=0; for(int i=head[x];i;i=edge[i].nxt){ int y=edge[i].to,v=edge[i].val; if(dep[y]==dep[x]+1&&v){ int now=dfs(y,min(rest,v)); edge[i].val-=now; edge[i^1].val+=now; flow+=now;rest-=now; if(!rest) break; } } return flow; } int dinic(){ int maxflow=0; while(bfs()) maxflow+=dfs(S,inf); return maxflow; }}void getspj(){ queue s; s.push(S);vis[S]=1; while(!s.empty()){ int x=s.front();s.pop(); for(int i=head[x];i;i=edge[i].nxt) if(!vis[edge[i].to]&&edge[i].val){ s.push(edge[i].to); vis[edge[i].to]=1; } } apr[S]=apr[T]=1;}int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();} while(isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f;}int main(){ n=read(),m=read(); S=n*2+1,T=S+1; for(int i=1;i<=n;i++) ru[i]=read(); for(int i=1;i<=n;i++) cu[i]=read(); for(int i=1;i<=n;i++){ ins(S,i,cu[i]);ins(i,S,0); ins(i+n,T,ru[i]);ins(T,i+n,0); } for(int x,y,i=1;i<=m;i++){ x=read(),y=read(); ins(x,n+y,inf); ins(n+y,x,0); } using namespace Network_Flow; printf("%d\n",dinic());getspj(); for(int i=1;i<=n;i++) for(int j=head[i];j;j=edge[j].nxt){ int y=edge[j].to; if(!vis[i]&&!vis[y]&&!apr[i]){ sec[++t2]=i; ans++;apr[i]=1; } if(!apr[y]&&vis[y]){ fst[++t1]=y%n; if(!fst[t1]) fst[t1]=n; ans++;apr[y]=1; } } printf("%d\n",ans); for(int i=1;i<=t1;i++) printf("%d +\n",fst[i]); for(int i=1;i<=t2;i++) printf("%d -\n",sec[i]); return 0;}