BZOJ 3876 [Ahoi2014] 支线剧情 【带上下界网络流】
【题解】
裸上下界费用流即可。
发现以前写的费用流都有问题。。。gg
# include <stdio.h> # include <string.h> # include <queue> using namespace std; const int M=1000010,Me=1010; int tot=1,head[Me],next[M],to[M],flow[M],w[M],S,T,pre[Me],d[Me],from[Me]; bool vis[Me]; const int INF=0x3f3f3f3f; inline void add(int u,int v,int fl,int ws) { ++tot; next[tot]=head[u]; head[u]=tot; to[tot]=v; flow[tot]=fl; w[tot]=ws; } inline void Add(int u,int v,int fl,int ws) { add(u,v,fl,ws); add(v,u,0,-ws); } int ans=0; inline bool spfa() { queue<int> q; while(!q.empty()) q.pop(); memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); d[S]=0; vis[S]=1; q.push(S); while(!q.empty()) { int top=q.front(); q.pop(); vis[top]=0; for (int i=head[top];i;i=next[i]) { if(d[top]+w[i]<d[to[i]]&&flow[i]) { d[to[i]]=d[top]+w[i]; if(!vis[to[i]]) { vis[to[i]]=1; q.push(to[i]); } pre[to[i]]=i; from[to[i]]=top; } } } return d[T]!=INF; } inline void mcf() { int xm=1e9; for (int i=T;i!=S;i=from[i]) xm=min(xm,flow[pre[i]]); for (int i=T;i!=S;i=from[i]) { flow[pre[i]]-=xm; flow[pre[i]^1]+=xm; } ans=ans+d[T]*xm; } inline long long g() { while(spfa()) mcf(); } int n; int main() { scanf("%d",&n); S=0,T=Me-1; for (int i=1,b,Te,t;i<=n;++i) { scanf("%d",&Te); Add(i,1,INF,0); for (int j=1;j<=Te;++j) { scanf("%d%d",&b,&t); Add(i,b,INF,t); Add(S,b,1,t); Add(i,T,1,0); } } g(); printf("%d\n",ans); return 0; } /* 6 2 2 1 3 2 2 4 3 5 4 2 5 5 6 6 0 0 0 */