KWAY - Trao đổi thông tin

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define MAX   111
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define	REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi   first
#define se   second
using namespace std;
const int INF=(int)1e9+7;
typedef pair<int,int> ii;
void minimize(int &x,const int &y) {
	if (x>y) x=y;
}
class MaxFlowMinCost {
	public:
	struct edge {
		int from,to,capa,flow,cost;
		edge() {
			from=0;to=0;capa=0;flow=0;cost=0;
		}
		edge(int u,int v,int ca,int co) {
			from=u;to=v;capa=ca;flow=0;cost=co;
		}	
		int residual(void) const {
			return (capa-flow);
		}
	};
	vector<vector<int> > g;
	vector<edge> e;
	vector<int> d,tr;
	int n;
	MaxFlowMinCost() {
		n=0;
	}
	MaxFlowMinCost(int n) {
		this->n=n;
		g.assign(n+7,vector<int>());
		e.clear();
		d=vector<int>(n+7);
		tr=vector<int>(n+7);
	}
	void addedge(int u,int v,int ca,int co) {
		g[u].push_back(e.size());
		e.push_back(edge(u,v,ca,co));
		g[v].push_back(e.size());
		e.push_back(edge(v,u,0,-co));		
	}
	bool FordBellman(int s,int t) {
		FOR(i,1,n) {
			d[i]=INF;
			tr[i]=-1;
		}
		vector<bool> inq=vector<bool>(n+7,false);
		queue<int> q;
		while (!q.empty()) q.pop();
		q.push(s);inq[s]=true;d[s]=0;
		while (!q.empty()) {
			int u=q.front();q.pop();inq[u]=false;
			FORE(it,g[u]) if (e[*it].residual()>0) {
				int v=e[*it].to;
				if (d[v]>d[u]+e[*it].cost) {
					d[v]=d[u]+e[*it].cost;
					tr[v]=*it;
					if (!inq[v]) {
						q.push(v);
						inq[v]=true;
					}
				}
			}
		}
		return (d[t]<INF);
	}
	ii getflow(int s,int t) {
		int totflow=0;
		int totcost=0;
		while (FordBellman(s,t)) {
			int delta=INF;
			for (int u=t;u!=s;u=e[tr[u]].from) minimize(delta,e[tr[u]].residual());
			for (int u=t;u!=s;u=e[tr[u]].from) {
				e[tr[u]].flow+=delta;
				e[tr[u]^1].flow-=delta;
			}
			totflow+=delta;
			totcost+=delta*d[t];
		}
		return (ii(totflow,totcost));
	}
};
queue<int> q[MAX];
MaxFlowMinCost g;
int n,m,k,s,t;
void loadgraph(void) {
	scanf("%d",&n);
	scanf("%d",&m);
	scanf("%d",&k);
	scanf("%d",&s);
	scanf("%d",&t);
	g=MaxFlowMinCost(n+1);
	REP(i,m) {
		int u,v,c;
		scanf("%d",&u);
		scanf("%d",&v);
		scanf("%d",&c);
		g.addedge(u,v,1,c);
		g.addedge(v,u,1,c);
	}
	g.addedge(n+1,s,k,0);
}
void process(void) {
	ii res=g.getflow(n+1,t);
	if (res.fi<k) {
		printf("-1");
		return;
	}
	printf("%d\n",res.se);
	REP(i,g.e.size()) if (i%2==0 && g.e[i].flow>0 && g.e[i].from<=n) q[g.e[i].from].push(g.e[i].to);
	REP(zz,k) {
		vector<int> tmp;
		tmp.clear();
		int u=s;
		do {
			tmp.push_back(u);
			assert(!q[u].empty());
			int v=q[u].front();q[u].pop();
			u=v;
		}
		while (u!=t);
		tmp.push_back(t);
		printf("%d",tmp.size());
		FORE(it,tmp) printf(" %d",*it);
		printf("\n");
	}
}
int main(void) {
#ifndef ONLINE_JUDGE
	freopen("tmp.txt","r",stdin);
	printf("START\n");
#endif
	loadgraph();
	process();
	return 0;
}

Download