bzoj千题计划159：bzoj2055: 80人环游世界（有源汇上下界可行最小费用流）

http://www.lydsy.com/JudgeOnline/problem.php?id=2055

某个国家必须经过vi次，

可以转化为上下界都为vi的边

对这张图做有源汇上下界可行最小费用流

按无源汇上下界可行流建好图，跑超级源点到超级汇点的最小费用最大流即可

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 205

#define M 10500

const int inf=1e9;

int src,decc;

int S,T;

int tot=;

int front[N],to[M<<],nxt[M<<],cap[M<<],val[M<<],from[M<<];

int cost;

int dis[N];

bool vis[N];

void read(int &x)

{

    x=;  int f=; char c=getchar();

    while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

    x*=f;

}

void add(int u,int v,int w,int f)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; cap[tot]=w; val[tot]=f;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; cap[tot]=; val[tot]=-f;

}

int agument(int now,int flow)

{

    vis[now]=true;

    if(now==T)

    {

        cost-=dis[S]*flow;

        return flow;

    }

    int delta;

    for(int i=front[now];i;i=nxt[i])

    {

        if(cap[i] && !vis[to[i]] && dis[to[i]]==dis[now]+val[i])

        {

            delta=agument(to[i],min(flow,cap[i]));

            if(delta)

            {

                cap[i]-=delta;

                cap[i^]+=delta;

                return delta;

            }

        }

    }

    return ;

}

bool retreat()

{

    if(vis[T]) return true;

    int mi=inf;

    for(int i=;i<=tot;++i)

        if(cap[i] && vis[from[i]] && !vis[to[i]])

            mi=min(mi,dis[from[i]]+val[i]-dis[to[i]]);

    if(mi==inf) return false;

    for(int i=;i<=T;++i)

        if(vis[i]) dis[i]-=mi;

    return true;

}

void zkw()

{

    do

    {

        memset(vis,false,sizeof(vis));

        agument(S,inf);

    }while(retreat());

    cout<<cost;

}

int main()

{

    int n,m;

    read(n); read(m);

    src=; decc=(n<<|)+;

    int ss=;

    S=decc+; T=S+;

    add(src,T,m,);

    add(S,ss,m,);

    int x;

    for(int i=;i<=n;++i)

    {

        read(x);

        add(ss,i<<,m,);

        add(i<<|,decc,m,);

        add(i<<,T,x,);

        add(S,i<<|,x,);

    }

    int k;

    for(int i=;i<n;++i)

    {

        for(int j=i+;j<=n;++j)

        {

            read(x);

            if(x==-) continue;

            add(i<<|,j<<,m,x);

        }

    }

    add(decc,src,m,);

    zkw();

}