BZOJ-1927: [Sdoi2010]星际竞速

[文章目录]

Description

给你一张n个点,m条边的图,你能从连有边的两点中编号小的点走到编号大的点,并且花费一定代价,也可以直接到瞬移到定点,花费相应代价。问经过所有点都恰好一次的最小代价。n<=800 m<=15000

费用流。
每个点只能走向另一个点一次。类似餐巾计划,s向点x连边,流量为1,x向出边连的点连边,费用为边权。s向每个点连边,流量为1,费用为瞬移的代价。每个向t连边流量为1。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t,ans;
int head[1700],to[40000],nxt[40000],f[40000],w[40000],cnt=1;
inline void add(int x,int y,int z,int ww)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z; w[cnt]=ww;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0; w[cnt]=-ww;
}
queue<int>q;
int path[1700],dis[1700];
bool vis[1700];
bool spfa()
{
    memset(dis,0x3f,sizeof dis);
    while(!q.empty()) q.pop();
    dis[s]=0; q.push(s); vis[s]=1; int x;
    while(!q.empty())
    {
        x=q.front(); q.pop(); vis[x]=0;
        for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[x]+w[i]<dis[to[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;
}
inline void mincost()
{
    int flow;
    while(spfa())
    {
        flow=inf;
        for(int i=t;i!=s;i=to[path[i]]) flow=min(flow,f[path[i]^1]);
        for(int 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%d",&n,&m); s=(n<<1)+1; t=s+1;
    int x,y,z;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        add(s,i,1,x);
        add(i,t,1,0);
        add(s,n+i,1,0);
    }
    while(m--)
    {
        scanf("%d%d%d",&x,&y,&z); if(x>y) swap(x,y);
        add(n+x,y,1,z);
    }
    mincost(); printf("%d",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注