BZOJ 1930 SHOI 2003 pacman 吃豆豆 費用流

BZOJ 1930 SHOI 2003 pacman 吃豆豆 費用流

題目大意：給出一些平面上的點，你有兩個吃豆人，從一個點出發，這個吃豆人可以吃到當前點右上方的點。問這兩個吃豆人最多可以吃到多少豆子。

思路：我已經吧不相交的條件去掉了。。

不加優化的費用流模型很明顯

超級源->源 flow2 cost0

匯->超級匯 flow2 cost0

下面是拆點

i << 1 -> i << 1|1 flow1 cost1

對於從點i能夠到達點j的情況

i << 1|1 - > j << 1 flow1 cost0

然後跑樸素費用流，很明顯T掉了。一組能夠卡的數據，所有點都是(i,i)，2000個點跑這個算法會出現n^2條邊。

優化的出發點也是很明顯的。如果有三個點i,j,k能夠從i到j到k，那麼我們就肯定不會走i->k這條邊，那麼這個邊就不用加進去。

還有一些小細節，詳見代碼。

CODE：

#include 
#include 
#include 
#include 
#include 
#define MAX 4010
#define MAXE 4100000
#define INF 0x3f3f3f3f
#define S 0
#define _S 1
#define T (MAX - 1)
#define _T (MAX - 2)
using namespace std;

struct Point{
	int x,y;
	
	bool operator <(const Point &a)const {
		if(x == a.x)	return y < a.y;
		return x < a.x;
	}
	void Read() {
		scanf("%d%d",&x,&y);
	}
}point[MAX];

struct MinCostMaxFlow{
	int head[MAX],total;
	int next[MAXE],aim[MAXE],flow[MAXE],cost[MAXE];
	
	int f[MAX],from[MAX],p[MAX];
	bool v[MAX];
	
	MinCostMaxFlow() {
		total = 1;
	}
	void Add(int x,int y,int f,int c) {
		next[++total] = head[x];
		aim[total] = y;
		flow[total] = f;
		cost[total] = c;
		head[x] = total;
	}
	void Insert(int x,int y,int f,int c) {
		Add(x,y,f,c);
		Add(y,x,0,-c);
	}
	bool SPFA() {
		static queue q;
		while(!q.empty())	q.pop();
		memset(f,0x3f,sizeof(f));
		memset(v,false,sizeof(v));
		f[S] = 0;
		q.push(S);
		while(!q.empty()) {
			int x = q.front(); q.pop();
			v[x] = false;
			for(int i = head[x]; i; i = next[i])
				if(flow[i] && f[aim[i]] > f[x] + cost[i]) {
					f[aim[i]] = f[x] + cost[i];
					if(!v[aim[i]])
						v[aim[i]] = true,q.push(aim[i]);
					from[aim[i]] = x;
					p[aim[i]] = i;
				}
		}
		return f[T] != INF;
	}
	int EdmondsKarp() {
		int re = 0;
		while(SPFA()) {
			int max_flow = INF;
			for(int i = T; i != S; i = from[i])
				max_flow = min(max_flow,flow[p[i]]);
			for(int i = T; i != S; i = from[i]) {
				flow[p[i]] -= max_flow;
				flow[p[i]^1] += max_flow;
			}
			re += f[T] * max_flow;
		}
		return re;
	}
}solver;

int cnt;

int main()
{
	cin >> cnt;
	for(int i = 1; i <= cnt; ++i)
		point[i].Read();
	sort(point + 1,point + cnt + 1);
	for(int i = 1; i <= cnt; ++i) {
		int _min = INF;
		for(int j = i + 1; j <= cnt; ++j) {
			if(point[j].y < _min && point[j].y >= point[i].y)
				solver.Insert(i << 1|1,j << 1,2,0);
			if(point[j].y >= point[i].y)
				_min = min(_min,point[j].y);
		}
	}
	for(int i = 1; i <= cnt; ++i) {
		solver.Insert(i << 1,i << 1|1,1,-1);
		solver.Insert(i << 1,i << 1|1,1,0);
		solver.Insert(_S,i << 1,1,0);
		solver.Insert(i << 1|1,_T,1,0);
	}
	solver.Insert(S,_S,2,0);
	solver.Insert(_T,T,2,0);
	cout << -solver.EdmondsKarp() << endl;
	return 0;
}