思路：
这题考的是最大闭权图。只要知道怎么求最大闭权图就知道怎么做。但好像有点卡模版，要高效的模版才行。
#include <iostream> #include <stdio.h> #include <string.h> #define Maxn 6010 #define Maxm 200000 #define LL __int64 #define Abs(a) (a)>0?(a):(-a) using namespace std; struct Edge{ int from,to,next; LL val; }edge[Maxm]; LL value[Maxn],inf=0; int index[Maxn],work[Maxn],dis[Maxn],q[Maxn],e,vi[Maxn]; inline void addedge(int from,int to,LL val)//有向边 { edge[e].from=from; edge[e].to=to; edge[e].val=val; edge[e].next=index[from]; index[from]=e++; edge[e].from=to; edge[e].to=from; edge[e].val=0; edge[e].next=index[to]; index[to]=e++; } void init() { e=0; memset(index,-1,sizeof(index)); memset(vi,0,sizeof(vi)); inf=0; } void add(int u,int v,LL c) { edge[e].to=v;edge[e].val=c;edge[e].next=index[u];index[u]=e++; edge[e].to=u;edge[e].val=0;edge[e].next=index[v];index[v]=e++; } void DFS(int u) { vi[u]=1; int i,v; for(i=index[u];i!=-1;i=edge[i].next) if(edge[i].val&&!vi[edge[i].to]) DFS(edge[i].to); } int bfs(int S,int T) { int rear=0; memset(dis,-1,sizeof(dis)); dis[S]=0;q[rear++]=S; for(int i=0;i<rear;i++) { for(int j=index[q[i]];j!=-1;j=edge[j].next) { if(edge[j].val&&dis[edge[j].to]==-1) { dis[edge[j].to]=dis[q[i]]+1; q[rear++]=edge[j].to; if(edge[j].to==T) return 1; } } } return 0; } LL dfs(int cur,LL a,int T) { if(cur==T) return a; for(int &i=work[cur];i!=-1;i=edge[i].next) { if(edge[i].val&&dis[edge[i].to]==dis[cur]+1) { int t=dfs(edge[i].to,min(a,edge[i].val),T); if(t) { edge[i].val-=t; edge[i^1].val+=t; return t; } } } return 0; } LL Dinic(int S,int T) { LL ans=0; while(bfs(S,T)) { memcpy(work,index,sizeof(index)); while(int t=dfs(S,inf,T)) ans+=t; } return ans; } int main() { int n,m,i,a,b; LL sum=0; scanf("%d%d",&n,&m); init(); for(i=1;i<=n;i++) { scanf("%I64d",value+i); if(value[i]>0) { sum+=value[i]; addedge(0,i,value[i]); } else addedge(i,n+1,-value[i]); inf+=Abs(value[i]); } inf++; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b,inf); } LL ans=Dinic(0,n+1);//起始点和结束点 //DFS(0);//寻找S集合 int num=0; for(i=1;i<=n;i++) if(dis[i]>=0) num++; printf("%d %I64d ",num,sum-ans); return 0; }