[tyvj-2054][Nescafé29]四叶草魔杖 费用流

lyd讲的最小生成树的题。

道理我都懂，费用流多好写，又好调。但和一般费用流不一样的就是它走过一次后费用需调成0，但是再等回流，就恢复原状即可。

#include <queue>

#include <cstring>

#include <iostream>

#include <cstdio>

using namespace std;

const int N=5050,S=0,T=5005,inf=0x3f3f3f3f;

int n,m,a[N],sum,ecnt=1,head[N],dis[N],from[N];

bool inq[N];

struct Edge {

    int to,nxt,val,cost,from;

} e[1000010],fb[1000010];

void add(int bg,int ed,int val,int cost) {

    e[++ecnt].cost=cost;e[ecnt].from=bg;e[ecnt].nxt=head[bg];e[ecnt].to=ed;

    e[ecnt].val=val;head[bg]=ecnt;fb[ecnt]=e[ecnt];

}

void insert(int bg,int ed,int val,int cost) {

    add(bg,ed,val,cost);

    add(ed,bg,0,cost);

}

queue<int>q;

bool spfa() {

    q.push(S);

    std::memset(dis,0x3f,sizeof dis);

    std::memset(inq,0,sizeof inq);

    dis[S]=0;

    inq[S]=1;

    while(!q.empty()) {

        int u=q.front();

        q.pop();

        inq[u]=0;

        for(int i=head[u],v; i; i=e[i].nxt) {

            v=e[i].to;

            if(dis[v]>dis[u]+e[i].cost&&e[i].val) {

                dis[v]=dis[u]+e[i].cost;

                from[v]=i;

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

            }

        }

    }

    return dis[T]!=inf;

}

void min(int &x,int y) {x=x<y?x:y;}

int mincost,maxflow;

void mcf() {

    int x=inf,i=from[T];

    while(i) {min(x,e[i].val);i=from[e[i].from];}

    i=from[T];maxflow+=x;

    while(i) {

        e[i].val-=x;

        e[i^1].val+=x;

        mincost+=x*e[i].cost;

        if(e[i].val!=inf) {e[i].cost=0;e[i^1].cost=0;}

        else{e[i].cost=fb[i].cost;e[i^1].cost=fb[i^1].cost;}

        i=from[e[i].from];

    }

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1,x;i<=n;i++) {

		scanf("%d",&a[i]);

		if(a[i]>0)insert(S,i,a[i],0),sum+=a[i];

		else if(a[i]<0)insert(i,T,-a[i],0);

	}

	for(int i=1,s,t,x;i<=m;i++) scanf("%d%d%d",&s,&t,&x),add(++s,++t,inf,x),add(t,s,inf,x);//注意

	while(spfa()) mcf();

	if(maxflow==sum){

		mincost=0;

		for(int i=2;i<=ecnt;i++) {if(e[i].val&&e[i].val!=inf) mincost+=fb[i].cost;}

		cout<<mincost/2;

		return 0;

	}

	puts("Impossible");

}