UVa-10594 : Data Flow

問題概要

ノード数V(<100)、辺数E(<5000)の最小費用流を求める問題。

解法

最小費用流

acceptされたコード

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long int64;
typedef pair<int64, int> P;
struct edge{
	int to;
	int64 cap, cost;
	int rev;
};

const int MAX_V = 100;
const int MAX_M = 5000;
const int64 INF = 1LL<<61;

void init(){
	V = N;
	for(int i=0; i<N; i++){
		G[i].clear();
	}

	for(int i=0; i<M; i++){
		scanf("%d%d%lld", froms+i, tos+i, costs+i);
	}

	scanf("%lld%lld", &D, &K);

	for(int i=0; i<M; i++){
		froms[i]--; tos[i]--;
		add_edge(froms[i], tos[i], K, costs[i]);
		add_edge(tos[i], froms[i], K, costs[i]);
	}
}

int main(){
	while(scanf("%d%d", &N, &M) != EOF){
		init();
		int64 ans = min_cost_flow(0, N-1, D);
		if(ans == -1){
			puts("Impossible.");
		}
		else{
			printf("%lld\n", ans);
		}
	}

	return 0;
}