为什么这么慢呢。。。。
跑得如此持久。。。。。
大概就是一个最大权闭合子图的构图。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define inf 1000000007 #define maxv 2500 #define maxe 3000050 using namespace std; int n,m,k,x,y,g[maxv],nume=1,s,t,dis[maxv],sum=0,max_flow=0; struct edge { int v,f,nxt; }e[maxe]; queue <int> q; int read() { char ch;int data=0,f=1; while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0' && ch<='9') { data=data*10+ch-'0'; ch=getchar(); } return data*f; } void addedge(int u,int v,int f) { e[++nume].v=v;e[nume].f=f; e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0; e[nume].nxt=g[v];g[v]=nume; } bool bfs() { while (!q.empty()) q.pop(); for (register int i=s;i<=t;i++) dis[i]=inf; dis[s]=0;q.push(s); while (!q.empty()) { int head=q.front();q.pop(); for (register int i=g[head];i;i=e[i].nxt) { int v=e[i].v; if (e[i].f<=0) continue; if (dis[v]>dis[head]+1) { dis[v]=dis[head]+1; q.push(v); } } } return dis[t]!=inf; } int dinic(int x,int low) { if (x==t) return low; int ret=0; for (register int i=g[x];low && i;i=e[i].nxt) { int v=e[i].v; if ((e[i].f>0) && (dis[v]==dis[x]+1)) { int dd=dinic(v,min(low,e[i].f)); e[i].f-=dd;e[i^1].f+=dd; ret+=dd;low-=dd; } } if (!ret) dis[x]=inf; return ret; } int main() { n=read();m=read();s=0;t=n+m+1; for (register int i=1;i<=n;i++) { x=read();k=read();sum+=x;addedge(s,i,x); for (register int j=1;j<=k;j++) { x=read();y=read(); addedge(i,x+n,y); } } for (register int i=1;i<=m;i++) { x=read(); addedge(i+n,t,x); } while (bfs()) max_flow+=dinic(s,inf); printf("%d ",sum-max_flow); return 0; }