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; }