以下解释来源于其他牛人：

把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是
9
变出），就能保证出=入。如果每个点都是出=入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出=入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入>出的点u，连接边(u, t)、容量为x，对于出>入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度=出度的欧拉图。
由于是满流，所以每个入>出的点，都有x条边进来，将这些进来的边反向，OK，入=出了。对于出>入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出>入，和t连接的条件是入>出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入=出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。

如果这道题用矩阵，需要注意两点直接可能有有条边，容量要相加。

#include <stdio.h>
#include <string.h>
#define MAXN	210
#define MIN( a, b ) (a) > (b) ? (b) : (a)

int ent[MAXN];
int map[MAXN][MAXN], flow[MAXN][MAXN];

int EK( int num, int s, int t )
{
	int my_queue[MAXN], head, tail;
	int pre[MAXN], min_flow[MAXN];
	int ans = 0, i, k;
	memset( flow, 0, sizeof( flow ) );
	while ( 1 )
	{
		head = 0; tail = 1;
		my_queue[0] = s;
		memset( pre, -1, sizeof( pre ) );
		min_flow[s] = 0x7fffffff;
		pre[s] = -2;
		while ( head < tail )
		{
			k = my_queue[head++];
			for ( i = 0; i < num; ++i )
			{
				if ( pre[i]==-1 && flow[k][i]<map[k][i] )
				{
					my_queue[tail++] = i;
					pre[i] = k;
					min_flow[i] = MIN( min_flow[k], ( map[k][i]-flow[k][i] ) );
				}
			}
			if ( pre[t] != -1 )
			{
				k = t;
				while ( pre[k] >= 0 )
				{
					flow[pre[k]][k] += min_flow[t];
					flow[k][pre[k]] = -flow[pre[k]][k];
					k = pre[k];
				}
				break;
			}
		}
		if ( pre[t] == -1 ) return ans;
		else ans += min_flow[t];
	}
}

int main()
{
	int n, m, x, y, z, flag, cases;

	//freopen( "main.in", "r", stdin );

	scanf( "%d", &cases );
	while ( cases-- )
	{
		flag = 1;
		memset( ent, 0, sizeof( ent ) );
		memset( map, 0, sizeof( map ) );
		scanf( "%d%d", &n, &m );
		while ( m-- )
		{
			scanf( "%d%d%d", &x, &y, &z );
			ent[x]--; ent[y]++;
			if ( z == 0 ) map[x][y]++;
		}
		for ( z = 0, y = 1; y <= n && flag; ++y )
		{
			if ( ent[y] % 2 ) flag = 0;
			x = ent[y] / 2;
			if ( x > 0 )
			{
				map[y][n+1] = x; z += x;
			}
			else
				map[0][y] = -x;
		}
		if ( flag )	x = EK( n+2, 0, n+1 );
		if ( flag && x == z )
			printf( "possible\n" );
		else
			printf( "impossible\n" );
	}
	return 0;
}

#include <stdio.h>
#include <string.h>
#define MAXN 210
#define MAXM 2500

int MIN( int a, int b )
{
	return a > b ? b : a;
}

typedef struct node
{
	int f, c, u, v;
	struct node *rev, *next;
}tnode, *pnode;
tnode	edge[MAXM];
pnode	g[MAXN], pre[MAXN];
int		now, ent[MAXN];

void addEdge( int u, int v, int c, int k )
{
	pnode p = &edge[now];
	p->c = c; p->u = u; p->v = v;
	p->next = g[u];
	if ( k != -1 ) p->rev = &edge[k];
	g[u] = p; now++;
}

int EK( int num, int sour, int sink )
{
	int my_queue[MAXN], head, tail;
	int min_flow[MAXN], ans = 0;
	pnode p;

	while ( 1 )
	{
		head = 0; tail = 1;
		my_queue[0] = sour;
		memset( pre, 0, sizeof( pre ) );
		min_flow[sour] = 0x7fffffff;
		while ( head < tail )
		{
			int t = my_queue[head++];
			for ( p = g[t]; p; p = p->next )
			if ( pre[p->v] == 0 && p->f < p->c )
			{
				my_queue[tail++] = p->v;
				pre[p->v] = p;
				min_flow[p->v] = MIN( min_flow[t], ( p->c - p->f ) );
			}
			if ( pre[sink] )
			{
				for ( p = pre[sink]; p; p = pre[p->u] )
				{
					p->f += min_flow[sink];
					if ( p->rev ) p->rev->f = -p->f;
				}
				break;
			}
		}
		if ( pre[sink] == 0 ) return ans;
		else ans += min_flow[sink];
	}
}

int main()
{
	int n, m, x, y, z, flag, cases;
	//freopen( "main.in", "r", stdin );
	scanf( "%d", &cases );
	while ( cases-- )
	{
		flag = 1; now = 0;
		memset( ent, 0, sizeof( ent ) );
		memset( edge, 0, sizeof( edge ) );
		memset( g, 0, sizeof( g ) );
		scanf( "%d%d", &n, &m );
		while ( m-- )
		{
			scanf( "%d%d%d", &x, &y, &z );
			ent[x]--; ent[y]++;
			if ( z == 0 )
			{
				addEdge( x, y, 1, now+1 );
				addEdge( y, x, 0, now-1 );
			}
		}
		for ( z = 0, y = 1; y <= n && flag; ++y )
		if ( ent[y] != 0 )
		{
			if ( ent[y] & 1 ) flag = 0;
			x = ent[y] / 2;
			if ( x > 0 )
			{
				addEdge( y, n+1, x, -1 );
				z += x;
			}
			else
				addEdge( 0, y, -x, -1 );
		}
		if ( flag )	x = EK( n+2, 0, n+1 );
		if ( flag && x == z )
			printf( "possible\n" );
		else
			printf( "impossible\n" );
	}
	return 0;
}

题目大意：有4个长方形，放在一起，不能重叠，然后用一个长方形包围，这个长方形的面积最小为多少，宽度和长度为多少。如果有多组长宽都符合最小的话，那么按照p从大到小输出。

题目中提示只有题中给的6种情况，其他的情况都可以由这6种经过旋转，映像得到。

分析：题目中的6种中4和5其实是一种，旋转和映像得到的长方形应该和不经过旋转是一样的，所以只有5种情况。解题思想就是枚举每一种放置的顺序，然后进行判断，找到最小的面积。对于最后一种情况应该要根据4个长方形的长宽进行分类，具体见代码。

/*
ID: nazgul12
LANG: C
TASK: packrec
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct{ int x, y; } st;

st s[4], xy, sol[100];
int e[4], used[4] = {0};
int mini = 0x7fffffff, l;

void swap( st * t )
{
	int temp;
	temp = t->x; t->x = t->y; t->y = temp;
}

int mmax( int a, int b )
{
	return a > b ? a : b;
}

int sum( int l, int r )
{
	int t = 0, i;
	for ( i = l; i <= r; ++i )
		t += s[e[i]].x;
	return t;
}

int max( int l, int r )
{
	int t = 0, i;
	for ( i = l; i <= r; ++i )
		if ( s[e[i]].y > t )
			t = s[e[i]].y;
	return t;
}

void solve()
{
	int i;
	if ( xy.x > xy.y ) swap( &xy );
	if ( xy.x * xy.y > mini ) return;
	if ( xy.x * xy.y < mini )
	{
		l = 0; mini = xy.x * xy.y;
	}
	if ( xy.x * xy.y == mini )
	{
		for ( i = 0; i < l; ++i )
			if ( xy.x == sol[i].x )
				return;
	}
	sol[l].x = xy.x; sol[l].y = xy.y;
	l++;
}

void test()
{
	xy.x = sum( 0, 3 ); xy.y = max( 0, 3 );
	solve();
	xy.x = mmax( s[e[0]].x, sum( 1, 3 ) );
	xy.y = max( 1, 3 ) + s[e[0]].y;
	solve();
	xy.x = mmax( s[e[0]].x, sum( 1, 2 ) ) + s[e[3]].x;
	xy.y = mmax( s[e[3]].y, mmax( s[e[1]].y, s[e[2]].y ) + s[e[0]].y );
	solve();
	xy.x = mmax( s[e[1]].x, s[e[2]].x ) + s[e[0]].x + s[e[3]].x;
	xy.y = mmax( mmax( s[e[0]].y, s[e[3]].y ), s[e[1]].y + s[e[2]].y );
	solve();
	if ( s[e[1]].y <= s[e[0]].y && s[e[1]].x >= s[e[2]].x &&
		s[e[0]].x <= s[e[3]].x && s[e[3]].y <= s[e[2]].y )
		{
			xy.x = mmax( s[e[0]].x+s[e[1]].x , s[e[2]].x+s[e[3]].x );
			xy.y = mmax( s[e[0]].y+s[e[3]].y , s[e[1]].y+s[e[2]].y );
			solve();
		}
	if ( s[e[0]].x <= s[e[1]].x && s[e[2]].x <= s[e[3]].x )
	{
		xy.x = s[e[1]].x + s[e[3]].x;
		xy.y = mmax( s[e[0]].y+s[e[1]].y, s[e[2]].y+s[e[3]].y );
		solve();
	}
}

void dfs( int k )
{
	int i;
	if ( k == 4 ) test();
	else
	{
		for ( i = 0; i < 4; ++i )
			if ( used[i] == 0 )
			{
				e[k] = i; used[i] = 1;
				dfs( k + 1 );
				swap( s+i );
				dfs( k + 1 );
				swap( s+i );
				used[i] = 0;
			}
	}
}

int cmp( const void *a, const void *b )
{
	return ( ( st * )a )->x - ( ( st * )b )->x;
}

int main()
{
	int i;
	freopen( "packrec.in", "r", stdin );
	freopen( "packrec.out", "w", stdout );
	for ( i = 0; i < 4; ++i )
		scanf( "%d%d", &s[i].x, &s[i].y );
	dfs( 0 );
	printf( "%d\n", mini );
	qsort( sol, l, sizeof( sol[0] ), cmp );
	for ( i = 0; i < l; ++i )
		printf( "%d %d\n", sol[i].x, sol[i].y );
	return 0;
}

USACO TRAINING Section 1.1

Broken Necklace

You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:
1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead

The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).

Determine the point where the necklace should be broken so that the most number of beads can be collected.
Example

For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.

In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration will include the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.
PROGRAM NAME: beads
INPUT FORMATLine 1: N, the number of beads
Line 2: a string of N characters, each of which is r, b, or w

SAMPLE INPUT (file beads.in)
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
SAMPLE OUTPUT (file beads.out)
11
OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** *****

题目大意：你有一个项链，项链上的珠子颜色有红白蓝三种颜色，将项链从一个地方断开，然后展开成直线，然后从一头开始收集珠子，直到碰到其他颜色的，然后在另一头也一样收集。当从某个地方断开时，可以收集到最多的珠子，问最多收集到多少个。
注意：白色的珠子可以算成红色的或者是蓝色的。
样列：
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
从倒数6和7中间断开，可以收集到最多的个数11

1。最简单的方法就是从每个地方断开，然后统计最多的，复杂度O(n^2)。
2。贪心：输入的s是一个环，所以前后可以相连，为了方便，再复制一份在原来的后面成ss，这样收集到的珠子就应该是相邻的。为了收集到最多，断开点绝对不会是同一种颜色的珠子中间，只能是在边界上断开。因此直观的思想就是先计算在一起的相同颜色的有多少个，然后取相邻2种不同颜色最多的个数。比如题目中的样列brbrrrbbbrrrrrbrrbbrbbbbrrrrb，先复制成ss，brbrrrbbbrrrrrbrrbbrbbbbrrrrbbrbrrrbbbrrrrrbrrbbrbbbbrrrrb
统计在一起的相同颜色的珠子个数：1b1r1b3r3b5r1b2r2b1r4b4r2b1r1b3r3r5r1b2r2b1r4b4r1b，然后取相邻2种不同颜色最多的个数。由于白色的可以表示成红色或蓝色，所以白色的要特殊处理。但是像bbwwwbb中间的www应该直接算作b，这样才能取到最多。
下面代码中pre数组用于记录，pre[i]表示与s[i]颜色不同的珠子最近的位置，所以i-pre[i]就是这种颜色在一起的个数，再加上pre[i]到pre[pre[i]]的个数，就是能收集到的个数。其他解释见代码。

#include <stdio.h>
#include <string.h>

char s[701] = {0}, cur, flag; //cur用于标记当前珠子的颜色
int n, pre[701];

int main()
{
	int i, nn, t, k;
	freopen( "beads.in", "r", stdin );
	freopen( "beads.out", "w", stdout );
	memset( pre, -1, sizeof( pre ) );
	scanf( "%d%s", &n, s );
	//将s复制成ss
	for ( flag = cur = i = 0; i < n; ++i )
	{
		s[n+i] = s[i];
		//找到最开始的颜色		
		if ( !cur && s[i] != 'w' ) cur = s[i];
		//flag用于标示s是否只有一种颜色		
		if ( s[i] != s[0] ) flag = 1;
	}
	//如果只有一种颜色
	if ( !cur || !flag )
	{
		printf( "%d\n", n ); return 0;
	}
	//t用于记录当前颜色出现的开始位置
	i = 1; t = 0; k = -1; nn = ( n<<1 )-1;
	//k用于记录w是否可以表示成2种颜色，如果w是在同一种颜色的中间，k为-1,否则k为可以表示成2种颜色的最开始出现的位置
	//比如rrwwwb,则要记录最开始w出现的位置
	while ( i < nn )
	{
		if ( s[i]=='w' || s[i] == cur )
		{
			if ( k == -1 && s[i] == 'w' )
				k = i;
			else k = -1;
			i++;
		}
		else
		{
			pre[i-1] = t-1; cur = s[i];
			if ( k != -1 )
			{
				i = k; pre[i-1] = t-1;
			}
			t = ++i-1;
		}
	}
	t = 0;
	for ( i = 0; i < nn; ++i )
		if ( pre[i] != -1 )
		{
			k = i - pre[pre[i]];
			if ( t < k ) t = k;
		}
	printf( "%d\n", t );
	return 0;
}

题目大意：在一个建筑里面设有很多插座，但是每种插座只有一个。你有很多种设备，每一种设备要充电，必须插入对应的插座中，也就是有很多个插头。商店里面有很多种适配器，每种适配器一头插入一种插座里面，另外一头是另外一种插座，每种适配器的个数都是无限的。你尽量多的把设备可以同时充电，问还有几个设备无法充电。

分析：对于每种设备，如果存在对应的插座，则直接使用对应的插座。如果不存在，则用一个或多个适配器将那些不能直接用的插座转成可以使用的插座，对于某些无法转成的的设备对应的插头，则无法充电。按照这个死路，首先要记录哪些插座不能直接用，并且计算这些插座可以转换成哪些插座，还有哪些设备不能直接充电。因此插座和设备有一一对应关系，并且这些关系越多越好，由此可以想到要用二分图最大匹配。

需要注意：适配器中使用的插座或者插头，可能在建筑里面的插座以及设备插头都不相同，但是同样可以达到转换的效果，比如建筑里面有个插座类型为A，设备需要的插座为B，适配器可以通过A->C->B，这个C类型的，可能没在建筑里面的插座以及设备插头出现过。

代码如下：

#include <stdio.h>
#include <string.h>
#define MAXM 401

char rec[MAXM][25], isPlug[MAXM] = {0}, trans[MAXM][MAXM] = {0};
int iRece, iPlug, tot, iAdapt, m, n;
char path[MAXM][MAXM] = {0}, visit[MAXM];
int match[MAXM] = {0};

void inputReceptacles()
{
	int i;

	scanf( "%d", &iRece );
	for ( i = 0; i < iRece; ++i )
		scanf( "%s", rec[i] );
	tot = iRece;
}

int findSame( char *s, int k )
{
	int i;

	for ( i = 0; i < tot; ++i )
		if ( strcmp( s, rec[i] ) == 0 )
			return i;
	strcpy( rec[tot], s );
	isPlug[tot++] = k;
	return tot-1;
}

void inputPlug()
{
	char ch[25], s[25];
	int i, k;

	scanf( "%d", &iPlug );
	for ( i = 0; i < iPlug; ++i )
	{
		scanf( "%s%s", ch, s );
		k = findSame( s, 2 );
		if ( k != tot-1 ) isPlug[k]++;
	}
}

void inputAdapt()
{
	int i, a, b;
	char s1[250], s2[250];

	n = tot;
	scanf( "%d", &iAdapt );
	for ( i = 0; i < iAdapt; ++i )
	{
		scanf( "%s%s", s1, s2 );
		a = findSame( s1, 1 ); b = findSame( s2, 1 );
		trans[b][a] = 1;
	}
	for ( i = 0; i < tot; ++i )
		for ( a = 0; a < tot; ++a )
			for ( b = 0; b < tot; ++b )
				if ( trans[a][i] && trans[i][b] )
					trans[a][b] = 1;
	for ( m = i = 0; i < n; ++i )
		if ( isPlug[i] > 1 )
		{
			for ( a = 2; a <= isPlug[i]; ++a, ++m )
			{
				for ( b = 0; b < n; ++b )
					if ( isPlug[b] == 0 && trans[b][i] )
						path[b][m] = 1;
			}
		}
}

int SearchPath( int s )
{
	for ( int i = 0; i < m; i++ )
	{
		if ( path[s][i] && !visit[i] )
		{
			visit[i] = 1;
			if ( match[i] == 0 || SearchPath( match[i] ) )
			{
				match[i] = s;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int sum, i;

	inputReceptacles();
	inputPlug();
	inputAdapt();
	for ( sum = i = 0; i < n; ++i )
	{
		memset( visit, 0, sizeof( visit ) );
		if ( SearchPath( i ) ) sum++;
	}
	printf( "%d\n", m-sum );
	return 0;

二分匹配：构图很简单，注意构图的时候hole不能和其他的有边，设格子中2个格子x,y。x与y有一条边，y与x也有一条边，所以匹配数等于不是hole的个数。中间还可以判断不是hole的个数为奇数的时候直接输出NO，但好像时间少不了多少。

分别用了匈牙利算法（735+ms)和Hopcroft-Karp(157ms)算法

#include <algorithm>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 1230;
int d[4][2] = { -1, 0, 0, 1, 1, 0, 0, -1 };
int distx[N], disty[N], matex[N], matey[N], q[N], f[N];
vector<int> g[N];

bool BFS( int n )
{
	bool found = false;
	int fore = 0, rear = 0;
	for ( int i = 0; i < n; ++i )
	{
		if ( matex[i] == -1 )
			q[rear++] = i;//加入队列
		distx[i] = 0;//要匹配的一边
		disty[i] = 0;//要匹配的另一边
	}
	for ( ; fore < rear; ++fore )//队列不空
	{
		int x = q[fore];//从队列从取出x，并扩展
		for ( vector<int>::const_iterator it = g[x].begin(); it != g[x].end(); ++it )
		{//
			if ( !disty[*it] )//选择未访问的点，因为是要求不相交的增广路径
			{
				disty[*it] = distx[x]+1;//至少是1，
				if ( matey[*it] == -1 )//为被匹配的自由点，未被访问过，说明找到一条路径
					found = true;
				else
				{
					distx[matey[*it]] = disty[*it]+1;
					q[rear++] = matey[*it];
				}
			}
		}
	}
	return found;
}

bool DFS( int x )
{
	for ( vector<int>::const_iterator it = g[x].begin(); it != g[x].end(); ++it )
		if ( disty[*it] == distx[x] + 1 )
		{//走了这条边，但是不一定是增广路径
			disty[*it] = 0;
			if ( matey[*it] == -1 || DFS( matey[*it] ) )
				return matex[x] = *it, matey[*it] = x, true;
		}
	return false;
}

int Hopcroft_Karp( int n )
{
	int res = 0;
	fill_n( matex, n, -1 );
	fill_n( matey, n, -1 );
	while ( BFS( n ) )
		for ( int i = 0; i < n; ++i )//可能存在多个增广路径
			if ( matex[i] == -1 && DFS( i ) )//找到了一个增广路径
				++res;
	return res;
}

int main()
{
	int n, m, k, x, y, xx, yy, t, tt, kk;
	memset( f, 0, sizeof( f ) );
	scanf( "%d%d%d", &m, &n, &k );
	kk = m * n - k;
	while ( k-- )
	{
        scanf( "%d%d", &x, &y );
		f[(y-1)*n+x-1] = 1;
	}
	for ( y = 0; y < m; ++y )
	for ( x = 0; x < n; ++x )
	{
		tt = y*n + x;
		if ( !f[tt] )
		for ( k = 0; k < 4; ++k )
		{
			xx = x+d[k][1]; yy = y+d[k][0];
			if ( xx >= 0 && xx < n && yy >= 0 && yy < m )
			{
				t = yy*n+xx;
				if ( f[t] == 0 ) g[tt].push_back( t );
			}
		}
	}
    if ( Hopcroft_Karp( m * n ) == kk )
		printf( "YES\n" );
	else
		printf( "NO\n" );
	return 0;
}

#include <stdio.h>
#include <string.h>
#define MAXN 1230 //X最大个数
#define MAXM 1230  //Y最大个数
int d[4][2] = { -1, 0, 0, 1, 1, 0, 0, -1 };

char f[MAXN], path[MAXN][MAXM], visit[MAXM]; //path[i] [j]=true说明i到j有一条边
int match[MAXM]; //与Y中的点匹配的点标识
int SearchPath( int s, int m )
{
	int i;
	for ( i=0; i<m; i++ )
	{
		if ( path[s][i] && !visit[i] )//如果从s到i有边且Y中的i点没有被访问过
		{
			visit[i] = 1;
			if ( match[i]==-1 || SearchPath( match[i], m ) ) //查找可增广路并更新match数组
			{
				match[i] = s;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	int n, m, k, x, y, xx, yy, t, tt, kk, sum, i;
	memset( f, 0, sizeof( f ) );
	memset( path, 0, sizeof( path ) ); //将二分图初始化
	memset( match, -1, sizeof( match ) ); //匹配数组初始化
	memset( visit, 0, sizeof( visit ) );
	scanf( "%d%d%d", &m, &n, &k );
	kk = m * n - k;
	if ( kk & 1 ) goto label;
	while ( k-- )
	{
        scanf( "%d%d", &x, &y );
		f[(y-1)*n+x-1] = 1;
	}
	for ( y = 0; y < m; ++y )
	for ( x = 0; x < n; ++x )
	{
		tt = y*n + x;
		if ( !f[tt] )
		for ( k = 0; k < 4; ++k )
		{
			xx = x+d[k][1]; yy = y+d[k][0];
			if ( xx >= 0 && xx < n && yy >= 0 && yy < m )
			{
				t = yy*n+xx;
				if ( f[t] == 0 ) path[tt][t] = 1;
			}
		}
	}
	n = n * m;
    for ( sum = i = 0; i < n; ++i )
	{
		memset( visit, 0, sizeof( visit ) ); //已经访问了的点初始化
		if ( SearchPath( i, n ) ) sum++;
	}
	if ( sum == kk )
		printf( "YES\n" );
	else
label:	printf( "NO\n" );
	return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define MAXN 50001

struct node
{
	int x, y, z;
}ivl[MAXN];
int n, ql, l;
int q[MAXN], temp[MAXN], f[MAXN] = {0};

int cmp( const void *a, const void *b )
{
	return ( ( struct node * )b )->x - ( ( struct node * )a )->x;
}

int main()
{
	int c, i, j, t, ty;
	scanf( "%d", &n );
	for ( i = 0; i < n; ++i )
		scanf( "%d%d%d", &ivl[i].x, &ivl[i].y, &ivl[i].z );
	qsort( ivl, n, sizeof( ivl[0] ), cmp );
	for ( ql = i = 0; i < n; ++i )
	{
		t = ivl[i].z; ty = ivl[i].y;
		for ( c = 0, j = ql-1; j >= 0 && c < t; --j )
			if ( ty >= q[j] )
				c++;
		l = 0;
		for ( j = ivl[i].x; c < t; ++j )
			if ( !f[j] )
			{
				temp[l++] = j;
				f[j] = 1; ++c;
			}
		for ( j = l-1; j >= 0; --j )
			q[ql++] = temp[j];
	}
	printf( "%d\n", ql );
	return 0;
}

分析二：差分约束系统，对于整数i,用a[i]表示i以前有多少个在集合s中，则对于区间[x,y]有a[y]-a[x]>=z，即a[x]-a[y]<=-z，在图中表示从y到x有一条权值为-z的边。另外结果还要满足a[i+1]-a[i]<=1,a[i]-a[i+1]<=0。分别表示从i到i+1有一条权为1的边和i+1到i有一条权为0的边。204ms A了

#include <stdio.h>
#include <string.h>
#define MAXN 50101

struct node
{
	int v, d, next; //
}pot[160000];
int g[MAXN], pl;
int dis[MAXN], visit[MAXN], queue[MAXN], used[MAXN];

int spfa( int n, int s ) //点的个数，源点，汇点
{
	int top, tail, u, v, k;
	memset( dis, 0x7f, sizeof( dis ) );
	memset( visit, 0, sizeof( visit ) );
	dis[s] = 0; top = 0; tail = 1;
	queue[0] = s; visit[s] = 1;
	while ( top != tail ) //循环队列
	{
		u = queue[top]; visit[u] = 0;
		top++;
		if ( top == n ) top = 0;
		for ( k = g[u]; k != -1; k = pot[k].next )
		{
			v = pot[k].v;
			if ( dis[v] - pot[k].d > dis[u] )
			{
				dis[v] = dis[u] + pot[k].d;
				if ( !visit[v] )
				{
					queue[tail] = v; visit[v] = 1;
					tail++;
					if ( tail == n ) tail = 0;
				}
			}
		}
	}
	return dis[n-1] - dis[s];
}

void addEdge( int u, int v, int w )
{
	pot[pl].next = g[u];
	g[u] = pl;
	pot[pl].v = v; pot[pl].d = w;
	pl++;
}

int main()
{
	int u, v, w, n, m = 0, mi = 0x7fffffff;
	memset( g, -1, sizeof( g ) );
	memset( used, 0, sizeof( used ) );
	pl = 0;
	scanf( "%d", &n );
	while ( n-- )
	{
		scanf( "%d%d%d", &u, &v, &w );
		v++;
		addEdge( u, v, -w );
		if ( v > m ) m = v;
		if ( u < mi ) mi = u;
	}
	for ( u = mi; u <= m; ++u )
	{
		addEdge( u, u+1, 0 );
		addEdge( u+1, u, 1 );
	}
	printf( "%d\n", -spfa( m+1, mi ) );
	return 0;
}

本来以为用离散化可以速度更快的，结果更慢了。。。。时间：329ms

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 50101

struct node
{
	int v, d, next; //
}pot[160000];
struct _Queue
{
	int value, label;
}q[MAXN];
int hs[MAXN], queue[MAXN], g[MAXN], l, pl; //hash, queue, length of queue
int dis[MAXN], visit[MAXN];

int cmp( const void *a, const void *b )
{
	return ( ( struct _Queue * )b )->value - ( ( struct _Queue * )a )->value;
}

void spfa( int n, int s ) //点的个数，源点，汇点
{
	int top, tail, u, v, k;
	memset( dis, 0x7f, sizeof( dis ) );
	memset( visit, 0, sizeof( visit ) );
	dis[s] = 0; top = 0; tail = 1;
	queue[0] = s; visit[s] = 1;
	while ( top != tail ) //循环队列
	{
		u = queue[top]; visit[u] = 0;
		top++;
		if ( top == n ) top = 0;
		for ( k = g[u]; k != -1; k = pot[k].next )
		{
			v = pot[k].v;
			if ( dis[v] - pot[k].d > dis[u] )
			{
				dis[v] = dis[u] + pot[k].d;
				if ( !visit[v] )
				{
					queue[tail] = v; visit[v] = 1;
					tail++;
					if ( tail == n ) tail = 0;
				}
			}
		}
	}
}

void addEdge( int u, int v, int w )
{
	pot[pl].next = g[u];
	g[u] = pl;
	pot[pl].v = v; pot[pl].d = w;
	pl++;
}

int HashKy( int u )
{
	if ( hs[u] != -1 ) return hs[u];
	q[l].value = u; q[l].label = l;
	hs[u] = l; l++;
	return l-1;
}

void hashAddEdge( int u, int v, int w )
{
	addEdge( HashKy( u ), HashKy( v ), w );
}

int main()
{
	int u, v, w, n;
	memset( hs, 0, sizeof( hs ) );
	memset( g, -1, sizeof( g ) );
	memset( hs, -1, sizeof( hs ) );
	pl = l = 0;
	scanf( "%d", &n );
	while ( n-- )
	{
		scanf( "%d%d%d", &u, &v, &w );
		hashAddEdge( v+1, u, -w );
	}
	qsort( q, l, sizeof( q[0] ), cmp );
	for ( u = 0; u < l-1; ++u )
	{
		addEdge( q[u].label, q[u+1].label, 0 );
		addEdge( q[u+1].label, q[u].label, q[u].value-q[u+1].value );
	}
	spfa( l, q[0].label );
	printf( "%d\n", dis[q[0].label]-dis[q[l-1].label] );
	return 0;
}

http://poj.org/problem?id=2516

题目中有k种货物，将k种货物分开求，最后再相加。引入1个超级源点和超级汇点，源点到每个仓库的容量为每个仓库的容量，费用为0.仓库到每个人的容量无穷，费用为输入的。人到仓库容量为0,费用为输入值的负值。人到汇点容量为每个人的购买力，费用为0.

#include <stdio.h>
#include <string.h>
#define MAXN 52
#define MAXM 104
#define INF 0x7f7f7f7f
#define MIN( x, y ) x > y ? y : x

int n, m, k;
int r[MAXN][MAXN]; //shopkeeper's order
int s[MAXN][MAXN]; //each supply place's storage
int mat[MAXN][MAXN]; //each kind goods's cost
int flow[MAXM][MAXM], c[MAXM][MAXM]; //flow and capacity
int cost[MAXM][MAXM];
int flag, pre[MAXM], dis[MAXM], mf[MAXM];

void ConstructMap( int p, int t )
{
	int i, j;
	memset( c, 0, sizeof( c ) );
	memset( cost, 0, sizeof( cost ) );
	for ( i = 1; i <= m; ++i )
		c[0][i] = s[i][p];
	for ( i = 1; i <= m; ++i )
		for ( j = 1; j <= n; ++j )
		{
			c[i][j+m] = INF;
			cost[i][j+m] = mat[j][i];
			cost[j+m][i] = -mat[j][i];
		}
	for ( i = 1; i <= n; ++i )
		c[i+m][t] = r[i][p];
}

int spfa( int n, int s, int t )
{
	int queue[110], visit[110];
	int top, tail, u, i, v;
	memset( dis, 0x7f, sizeof( dis ) );
	memset( visit, 0, sizeof( visit ) );
	memset( pre, -1, sizeof( pre ) );
	dis[s] = 0; top = 0; tail = 1;
	queue[0] = s; visit[s] = 1;
	mf[s] = INF;
	while ( top != tail )
	{
		u = queue[top]; visit[u] = 0;
		top++;
		if ( top == n ) top = 0;
		for ( v = 0; v < n; ++v )
		if ( c[u][v] > flow[u][v] && dis[v] - cost[u][v] > dis[u] )
		{
			dis[v] = dis[u] + cost[u][v];
			mf[v] = MIN( mf[u], c[u][v]-flow[u][v] );
			pre[v] = u;
			if ( !visit[v] )
			{
				queue[tail] = v; visit[v] = 1;
				tail++;
				if ( tail == n ) tail = 0;
			}
		}
	}
	if ( pre[t] < 0 ) return 0;
	return 1;
}

int Min_Cost_Max_Flow( int n, int s, int t )
{
	int i, j, u, v, ans = 0;
	memset( flow, 0, sizeof( flow ) );
	while ( spfa( n, s, t ) )
 	{
		for ( u = pre[v=t]; v != 0; v = u, u = pre[v] )
		{
			flow[u][v] += mf[t];
			flow[v][u] -= mf[t];
		}
        ans += mf[t] * dis[t];
    }
	return ans;
}

int main()
{
	int i, j, p, sum, s1, s2;

	while ( 1 )
	{
		scanf( "%d%d%d", &n, &m, &k );
		if ( !n && !m && !k ) break;
		for ( i = 1; i <= n; ++i )
			for ( j = 1; j <= k; ++j )
				scanf( "%d", &r[i][j] );
		for ( i = 1; i <= m; ++i )
			for ( j = 1; j <= k; ++j )
				scanf( "%d", &s[i][j] );
		sum = 0; flag = 1;
		for ( j = 1; j <= k; ++j )
		{
			s1 = s2 = 0;
			for ( i = 1; i <= n; ++i )
				s1 += r[i][j];
			for ( i = 1; i <= m; ++i )
				s2 += s[i][j];
			if ( s1 > s2 )
			{
				flag = 0; break;
			}
		}
		for ( p = 1; p <= k; ++p )
		{
			for ( i = 1; i <= n; ++i )
				for ( j = 1; j <= m; ++j )
					scanf( "%d", &mat[i][j] );
			if ( !flag ) continue;
			ConstructMap( p, n+m+1 );
			sum += Min_Cost_Max_Flow( n+m+2, 0, n+m+1 );
		}
		printf( "%d\n", ( flag ? sum : -1 ) );
	}
	return 0;
}