[AHOI2014/JSOI2014]支线剧情

链接:https://www.luogu.com.cn/problem/P4044 题目描述:给定一个$DAG$，求若干条条路径，覆盖所有的点，并最小化路径的权值和。 题解：由于图是一个$DAG$，所以原问题可以转化为，求若干条路径，覆盖所有的边，并最小化路径的权值和。 仔细想想可以发现，其实就是求一个路径覆盖，每一条边被覆盖至少一次。这个问题可以用上下界有汇源最小费用可行流解决。 具体的，我们将每一条边设为流量上限为$inf$，下限为$1$就行了，由于图没有汇点，要将所有不为$1$的点向附加汇点$t$连边。 ``` #include #include #define inf 1e9 using namespace std; struct node { int v,nxt,data,cost; }; node edge[1000001]; bool used[100001]; int s,t,t0,ans,n,x,y,d[100001],incf[100001],prv[100001],head[100001],dis[100001],len; void add(int x,int y,int z,int w) { edge[++len].v=y; edge[len].data=z; edge[len].cost=w; edge[len].nxt=head[x]; head[x]=len; return; } bool spfa() { int top; queueq; q.push(s); incf[s]=1e9; for (int i=s+1;i<=t;++i) { dis[i]=1e9; used[i]=0; } while (!q.empty()) { top=q.front(); q.pop(); used[top]=0; for (int i=head[top];i>0;i=edge[i].nxt) if (edge[i].data&&dis[edge[i].v]>dis[top]+edge[i].cost) { dis[edge[i].v]=dis[top]+edge[i].cost; prv[edge[i].v]=i; incf[edge[i].v]=min(incf[top],edge[i].data); if (!used[edge[i].v]) { used[edge[i].v]=1; q.push(edge[i].v); } } } if (dis[t]==1e9) return 0; return 1; } int EK() { int x=t; while (x!=s) { edge[prv[x]].data-=incf[t]; edge[prv[x]^1].data+=incf[t]; x=edge[prv[x]^1].v; } return dis[t]*incf[t]; } int main() { int x,y,z; len=1; cin>>n; s=0; t0=n+1; t=n+2; for (int i=1;i<=n;++i) { cin>>x; while (x--) { cin>>y>>z; ans+=z; add(i,y,inf-1,z); add(y,i,0,-z); d[i]--; d[y]++; } } for (int i=2;i<=n;++i) { add(i,t0,inf,0); add(t0,i,0,0); } for (int i=1;i<=n;++i) { if (d[i]>0) { add(s,i,d[i],0); add(i,s,0,0); } else { add(i,t,-d[i],0); add(t,i,0,0); } } add(t0,1,inf,0); add(1,t0,0,0); while (spfa()) ans+=EK(); cout<