[文章目录]
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;
}