题目链接:https://www.luogu.com.cn/problem/P4043
题目大意:
思路:就是限制流量[1, inf]。有个坑点,就是汇点可以是任意点。不一定是剧情结束点。
例如:
#pragma GCC optimize(3, "Ofast", "inline") #include<bits/stdc++.h> #define re register using namespace std; const int maxn = 500 + 10; const int maxm=1e6+10; const int inf=1<<30; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++) char buf[1<<20],*p1=buf,*p2=buf; inline int read() { int f=0,fu=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') fu=-1; c=getchar(); } while(c>='0'&&c<='9') { f=(f<<3)+(f<<1)+c-48; c=getchar(); } return f*fu; } struct po { int to,dis,nxt,w; } edge[maxm<<1]; struct max_folw { int dis[maxn]; int vis[maxn]; int head[maxn]; int d[maxn]; int n,s,t,cut=-1; int ans=0, fy=0; void init(int N, int S, int T) { ans=0, fy=0; cut=-1; n=N, s=S, t=T; memset(head, -1, sizeof(head)); memset(d, 0, sizeof(d)); } void add_edge(int from,int to,int w,int dis) { edge[++cut].nxt=head[from]; edge[cut].to=to; edge[cut].w=w; edge[cut].dis=dis; head[from]=cut; } void add(int from,int to,int w,int dis) { add_edge(from,to,w,dis); add_edge(to,from,0,-dis); } void addlr(int from,int to,int w,int l, int r){ add(from,to,r-l,w); d[to]+=l, d[from]-=l; fy+=l*w; } bool spfa() { memset(vis,0,sizeof(vis)); for(re int i=0; i<=n; i++) dis[i]=inf; dis[t]=0; vis[t]=1; deque<int> q; q.push_back(t); while(!q.empty()) { int u=q.front(); vis[u]=0; q.pop_front(); for(re int i=head[u]; i!=-1; i=edge[i].nxt) { int v=edge[i].to; if(edge[i^1].w>0&&dis[v]>dis[u]-edge[i].dis) { dis[v]=dis[u]-edge[i].dis; if(!vis[v]) { vis[v]=1; if(!q.empty()&&dis[v]<dis[q.front()]) q.push_front(v); else q.push_back(v); } } } } return dis[s]<inf; } int dfs(int u,int low) { if(u==t) { vis[t]=1; return low; } int diss=0; vis[u]=1; for(re int i=head[u]; i!=-1; i=edge[i].nxt) { int v=edge[i].to; if(!vis[v]&&edge[i].w!=0&&dis[u]-edge[i].dis==dis[v]) { int check=dfs(v,min(edge[i].w,low)); if(check>0) { fy+=check*edge[i].dis; edge[i].w-=check; edge[i^1].w+=check; low-=check; diss+=check; if(low==0) break; } } } return diss; } void max_flow() { for(int i=0; i<=n; i++){ if(d[i]>0){ add(s, i, d[i], 0); } if(d[i]<0){ add(i, t, -d[i], 0); } } while(spfa()) { vis[t]=1; while(vis[t]) { memset(vis,0,sizeof(vis)); ans+=dfs(s,inf); } } } } flow; int d[maxn]; int main() { int n; scanf("%d", &n); int s=1, t=n+1, ss=n+2, tt=n+3;// flow.init(tt+5, ss, tt); for(int i=1; i<=n; i++){ int k; scanf("%d", &k); int from=i, to, fy, l=1, r=inf; flow.add(i, t, inf, 0); while(k--){ scanf("%d%d", &to, &fy); flow.addlr(i, to, fy, l, r); } } flow.add(t, s, inf, 0); flow.max_flow(); cout<<flow.fy<<endl; return 0; }