其实本来打算做最小费用最大流的题目前先来点模板题的,,,结果看到这道题二话不说(之前打太多了)敲了一个dinic,快写完了发现不对
我当时就这表情→ =_=你TM逗我
刚要删突然感觉dinic的模板中的bfs就相当于找每天边的权都为1的图上的最短路,稍稍改一下就能变成spfa,于是重新写了一下,但是函数名还是bfs。。。
然后又发现不对,最后要返回路径的,dfs也要改= =结果变成了非递归,但是函数名还是dfs。。。
于是一个看似是dinic,实则垃圾得不行的最小费用最大流就敲完了
然后调了一小会儿,最后发现我把入点和入点连了起来。。。难怪每次算出来都是直接飞
#include <cstdio>
#include <iostream>
#define INF 2147483647
using namespace std;
int n,m,N=,ans=,x,y,z,h,t,i,minflow,now;
int fir[],nex[],to[],flo[],cost[],d[],l[],father[];
bool que[];
inline void add(int a,int b,int c,int d){ nex[++N]=fir[a];fir[a]=N;to[N]=b;flo[N]=c;cost[N]=d;
nex[++N]=fir[b];fir[b]=N;to[N]=a;flo[N]=;cost[N]=-d;}
bool bfs()//其实是spfa
{
for(int i=;i<=n*+;i++) d[i]=INF;
for(h=,t=,l[]=n*+,d[n*+]=;h<=t;h++)
for (que[l[h]]=,i=fir[l[h]];i;i=nex[i])
if(flo[i] && d[to[i]]>d[l[h]]+cost[i])
{
father[to[i]]=i;//注意father存的是边
d[to[i]]=d[l[h]]+cost[i];
if (!que[to[i]])
l[++t]=to[i],que[to[i]]=;
}
return d[n*+]!=INF;
} void dfs()//其实写成了非递归
{
for(minflow=INF,now=n*+;now!=n*+;now=to[father[now]^])
minflow=min(minflow,flo[father[now]]);
for(now=n*+;now!=n*+;now=to[father[now]^])
ans+=cost[father[now]],flo[father[now]]-=minflow,flo[father[now]^]+=minflow;
} int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
scanf("%d",&x),add(n*+,i+n,,x);
for (int i=;i<=n;i++)
add(n*+,i,,);
for (int i=;i<=m;i++)
scanf("%d%d%d",&x,&y,&z),add(min(x,y),max(x,y)+n,,z);
for (int i=;i<=n;i++)
add(i+n,n*+,,);
while (bfs()) dfs();
printf("%d\n",ans);
return ;
}