[POJ] 3680 Intervals

題目網址: http://poj.org/problem?id=3680

題意: 給定N個帶權重Wi的開區間，求開區間重疊不超過K個的最大權重總和。



解法: 先將給定區間的值離散化，將離散化後的每個值當成一個點，且額外增加一起點S、一終點T，然後在(S,V1),(V1,V2)...(VN,T)建立有向邊且容量為K權重為0，接著在每個開區間(Vi,Vj)建立有向邊容量為1權重為-Wi，接著以此圖求最小費用最大流，輸出負的最小費用即可。

TAG: MinCostMaxFlow, 離散化

注意: 網路流的題目都要非常注意點、邊的數目所需分配的空間。

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	#include <queue>
	using namespace std;
	#define N 510
	#define M 1010
	#define INF 1e7
	typedef queue<int> QI;
	struct Edge {
	int u, v;
	int c, p;
	int next;
	Edge( int _u = 0, int _v = 0, int _c = 0, int _p = 0, int _next = -1 ):
	u(_u), v(_v), c(_c), p(_p), next(_next) {}
	};
	int T, n, k;
	int x[N];
	int xl;
	int w[N];
	int cor[N][2];
	int vn;
	Edge edge[M*3];
	int eHead[N];
	int eCnt;
	int cost, flow;
	int s, t;
	int trans( int v )
	{
	static int l, r, mid;
	l = 0; r = xl-1;
	while( l <= r ) {
	mid = (l+r)>>1;
	if( x[mid] == v ) return mid;
	if( x[mid] > v ) r = mid-1;
	else l = mid+1;
	}
	}
	void addEdge( int u, int v, int c, int p )
	{
	edge[eCnt] = Edge( u, v, c, p, eHead[u] );
	eHead[u] = eCnt++;
	edge[eCnt] = Edge( v, u, 0, -p, eHead[v] );
	eHead[v] = eCnt++;
	}
	void minCostMaxFlow( void )
	{
	static int i, j, now, ne, pre[N], minf;
	static int d[N];
	static bool inQ[N];
	static Edge e;
	flow = 0; cost = 0;
	while( 1 ) {
	for( i = 0, j = vn; i < j; ++i ) d[i] = INF;
	memset( inQ, 0, sizeof(inQ) );
	memset( pre, -1, sizeof(pre) );
	QI que; que.push(s); inQ[s] = true; d[s] = 0;
	while( !que.empty() ) {
	now = que.front(); que.pop();
	inQ[now] = false;
	for( ne = eHead[now]; ne != -1; ne = edge[ne].next ) {
	e = edge[ne];
	if( e.c && d[now]+e.p < d[e.v] ) {
	d[e.v] = d[now]+e.p;
	pre[e.v] = ne;
	if( !inQ[e.v] ) {
	que.push(e.v);
	inQ[e.v] = true;
	}
	}
	}
	}
	if( d[t] == INF ) return;
	for( now = t, minf = INF; now != s; now = edge[pre[now]].u )
	minf = min( minf, edge[pre[now]].c );
	flow += minf;
	cost += minf*d[t];
	for( now = t; now != s; now = edge[pre[now]].u ) {
	edge[pre[now]].c -= minf;
	edge[pre[now]^1].c += minf;
	}
	}
	}
	void init( void )
	{
	static int i;
	scanf( "%d%d", &n, &k );
	xl = 0;
	for( i = 0; i < n; ++i ) {
	scanf( "%d%d%d", &cor[i][0], &cor[i][1], &w[i] );
	x[xl++] = cor[i][0]; x[xl++] = cor[i][1];
	}
	sort( x, x+xl );
	xl = unique( x, x+xl )-x;
	s = xl; t = xl+1; vn = xl+2;
	eCnt = 0;
	memset( eHead, -1, sizeof(eHead) );
	addEdge( s, 0, k, 0 );
	addEdge( xl-1, t, k, 0 );
	for( i = 0; i < xl-1; ++i ) addEdge( i, i+1, k, 0 );
	for( i = 0; i < n; ++i ) addEdge( trans(cor[i][0]), trans(cor[i][1]), 1, -w[i] );
	}
	int main( void )
	{
	int i;
	scanf( "%d", &T );
	while( T-- ) {
	init();
	minCostMaxFlow();
	printf( "%d\n", -cost );
	}
	return 0;
	}

view raw Intervals.cpp hosted with ❤ by GitHub