bzoj 1927 [Sdoi2010]星际竞速——网络流

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1927

每个点拆点保证只经过一次。

主要是如果经过了这个点，这个点应该向汇点流过去表示经过了它。但这样就难以表示它接着往别的点走了。

发现是DAG。而且每个点都会要求经过。所以不妨认为连向它的点一定是已经经过了的点。

源点向每个点的入点连容量为1的边，表示走到这个点之后只能选择一个孩子走过去。从连向自己的点的入点向自己的出点连边，表示它能让自己“被经过”即流向汇点。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=,M=,INF=N;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mn(int a,int b){return a<b?a:b;}

int n,m,t,hd[N],xnt=,nxt[M],to[M],cap[M],w[M];

int dis[N],pre[N],info[N],ans; bool ins[N];

queue<int> q;

void add(int x,int y,int d)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;cap[xnt]=;w[xnt]=d;

  to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;cap[xnt]=;w[xnt]=-d;

}

bool spfa()

{

  memset(ins,,sizeof ins);

  memset(dis,0x3f,sizeof dis);

  q.push();ins[]=;dis[]=;info[]=INF;info[t]=;

  while(q.size())

    {

      int k=q.front();q.pop();ins[k]=;

      for(int i=hd[k],v;i;i=nxt[i])

    if(cap[i]&&dis[v=to[i]]>dis[k]+w[i])

      {

        dis[v]=dis[k]+w[i];

        pre[v]=i;info[v]=Mn(info[k],cap[i]);

        if(!ins[v])q.push(v),ins[v]=;

      }

    }

  return info[t];

}

void ek()

{

  int s=info[t];

  for(int i=pre[t];i;i=pre[to[i^]])

    {

      ans+=s*w[i];cap[i]-=s;cap[i^]+=s;

    }

}

int main()

{

  n=rdn();m=rdn();t=(n<<)+;

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

    d=rdn(),add(,i,),add(,j,d),add(j,t,);

  for(int i=,u,v,d;i<=m;i++)

    {

      u=rdn();v=rdn();d=rdn();

      if(u>v)swap(u,v); add(u,v+n,d);

    }

  while(spfa())ek();

  printf("%d\n",ans);

  return ;

}