常规题目;
最小费用最大流,如果是无向图的话,一定用邻接表去做。
代码:
//最小费用最大流,注意建图的edge都是双向的 #include <cstdio> #include <cstring> #include <queue> #include <iostream> using namespace std; const int INF = 0x3fffffff; const int N = 350; int S = 0, E; int n, m, k, p, id; int head[N], pre[N], r[N]; struct Edge { int u, v, w, cap, flow, next; }e[200000]; void add( int u, int v, int w, int cap, int flow ) { e[id].next = head[u], e[id].u = u, e[id].v = v, e[id].w = w, e[id].cap = cap, e[id].flow = 0; head[u] = id++; e[id].next = head[v], e[id].u = v, e[id].v = u, e[id].w = -w, e[id].cap = 0, e[id].flow = 0; } int maxFlow() { bool vis[N]; int d[N]; int c = 0, f = 0; queue <int> q; while ( 1 ) { for ( int i = 0; i <= E; ++i ) d[i] = INF; d[S] = 0; memset( vis, 0, sizeof(vis) ); vis[S] = true; q.push( S ); while ( !q.empty() ) { int u = q.front(); q.pop(); vis[u] = false; for ( int i = head[u]; i != -1; i = e[i].next ) { int v = e[i].v, cap = e[i].cap, flow = e[i].flow, w = e[i].w; if ( cap > flow && d[v] > d[u] + w ) { d[v] = d[u] + w; pre[v] = u; r[v] = i; if ( !vis[v] ) { vis[v] = true; q.push(v); } } } } if ( d[E] == INF ) break; int a = INF; for ( int u = E; u != S; u = pre[u] ) { int ei = r[u]; a = min( a, e[ei].cap - e[ei].flow ); } for ( int u = E; u != S; u = pre[u] ) { int ei = r[u]; e[ei].flow += a; e[ei^1].flow -= a; } c += d[E]*a; f += a; } return c; } int main() { while ( scanf("%d%d%d%d", &n, &m, &k, &p) != EOF ) { memset( head, -1, sizeof(head)); E = n + m + 1; id = 0; for ( int i = 1, s; i <= n; ++i ) { scanf("%d", &s); add( S, s, 0, 1, 0 ); add( s, S, 0, 0, 0 ); } for ( int i = 1, s, e, w; i <= k; ++i) { scanf("%d%d%d", &s, &e, &w); add( s, e, w, INF, 0 ); add( s, e, w, INF, 0 ); } for ( int i = 1, s, e, w; i <= p; ++i) { scanf("%d%d%d", &s, &e, &w); add( s+m, e, w, INF, 0 ); add( e, s+m, w, INF, 0 ); } for ( int i = m+1; i <= m+n; ++i ) { add( i, E, 0, 1, 0 ); add( E, i, 0, 0, 0 ); } printf("%d\n", maxFlow()); } }