BZOJ-3876: [Ahoi2014&Jsoi2014]支线剧情

Description

给你一张n个点拓扑图，每次可以从起点开始经过一条路径到达一个点跳出。询问最小路程使得每条边都被经过至少一次。n<=300

有上下界最小费用流，按照原图建图，边权即为花费，流量下界为1。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
#define N 510
int s,t,S,T,ss,tt,n,ans;
int head[N],to[30000],nxt[30000],f[30000],w[30000],cnt=1;
inline void add(int x,int y,int ff,int ww)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=ff; w[cnt]=ww;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0; w[cnt]=-ww;
}
int dis[N],path[N];
bool vis[N];
queue<int>q;
bool spfa()
{
    while(!q.empty()) q.pop();
    memset(dis,0x3f,sizeof dis);
    dis[s]=0; q.push(s); int x,i;
    while(!q.empty())
    {
        x=q.front(); q.pop(); vis[x]=0;
        for(i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]>dis[x]+w[i])
        {
            dis[to[i]]=dis[x]+w[i];
            path[to[i]]=i^1;
            if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
        }
    }
    return dis[t]<inf;
}
void mincost()
{
    int i,flow;
    while(spfa())
    {
        for(flow=inf,i=t;i!=s;i=to[path[i]]) flow=min(flow,f[path[i]^1]);
        for(i=t;i!=s;i=to[path[i]])
        {
            f[path[i]]+=flow; f[path[i]^1]-=flow;
            ans+=w[path[i]^1]*flow;
        }
    }
}
int main()
{
    scanf("%d",&n); ss=n+1; tt=n+2; S=n+3; T=n+4;
    int i,k,x,y;
    for(i=1;i<=n;++i)
    {
        scanf("%d",&k); if(k) add(i,T,k,0);
        while(k--)
        {
            scanf("%d%d",&x,&y);
            add(S,x,1,y);
            add(i,x,inf,y);
        }
    }
    add(ss,1,inf,0);
    for(i=2;i<=n;++i) add(i,tt,inf,0);
    add(tt,ss,inf,0);
    s=S; t=T; mincost();
    printf("%d\n",ans);
    return 0;
}