POJ - nazgul's Blog
POJ 1637 Sightseeing tour
以下解释来源于其他牛人：
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以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;
}
POJ 1087 A Plug for UNIX
题目大意：在一个建筑里面设有很多插座，但是每种插座只有一个。你有很多种设备，每一种设备要充电，必须插入对应的插座中，也就是有很多个插头。商店里面有很多种适配器，每种适配器一头插入一种插座里面，另外一头是另外一种插座，每种适配器的个数都是无限的。你尽量多的把设备可以同时充电，问还有几个设备无法充电。
分析：对于每种设备，如果存在对应的插座，则直接使用对应的插座。如果不存在，则用一个或多个适配器将那些不能直接用的插座转成可以使用的插座，对于某些无法转成的的设备对应的插头，则无法充电。按照这个死路，首先要记录哪些插座不能直接用，并且计算这些插座可以转换成哪些插座，还有哪些设备不能直接充电。因此插座和设备有一一对应关系，并且这些关系越多越好，由此可以想到要用二分图最大匹配。
需要注意：适配器中使用的插座或者插头，可能在建筑里面的插座以及设备插头都不相同，但是同样可以达到转换的效果，比如建筑里面有个插座类型为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;
pku 3013
题目不太好理解.思路:首先对于一个点Vi,有多少个点以它为后代,经分析可以知道从root到Vi的最短路径中所有的点都会把Vi当做后代点.对于其他每个点,Vi贡献应该为sum{weight[Vi]*dist[k],k是所有以Vi为后代的点}.
题目需要注意几点:
1. root到每个点的距离可能超过int,所以对于dist要用long long.
2. 点的个数为0或1个的时候要特殊判断.
3. 边是双向的.
看其他牛的解题报告的时候,发现自己写个输入函数更快,所以也自己写了个.最后125ms.
#include <stdio.h>
#include <string.h>
#define MAXN 51001
#define NIL 922337203685477580
typedef long long IIL;
struct _Node
{
int v, next, w;
}edge[2*MAXN+100];
int queue[MAXN+100], visit[MAXN], g[MAXN], weight[MAXN];
IIL dist[MAXN];
int v, e, p;
void SPFA( int s, int N )
{
int h, t, x, i, tt, vv;
IIL *temp = dist;
for ( i = 0; i <= N; ++i )
*temp++ = NIL;
memset( visit, 0, sizeof( visit ) );
dist[s] = 0;
h = 0; t = 1;
queue[0] = s; visit[s] = 1;
while ( h != t )
{
x = queue[h]; visit[x] = 0;
for ( i = g[x]; i != -1; i = edge[i].next )
{
tt = edge[i].w; vv = edge[i].v;
if ( dist[vv] - tt > dist[x] )
{
dist[vv] = dist[x] + tt;
if ( !visit[vv] )
{
queue[t] = vv; visit[vv] = 1;
if ( ++t >= N ) t = 0;
}
}
}
if ( ++h >= N ) h = 0;
}
}
void addEdge( int u, int v, int w )
{
edge[p].next = g[u];
edge[p].v = v; edge[p].w = w;
g[u] = p++;
}
int GetInt()
{
char ch;
int t = 0;
while ( ( ch = getchar() ) != EOF )
{
if ( ch >= '0' && ch <= '9' ) break;
}
do
{
if ( ch < '0' || ch > '9' ) return t;
t = ( t << 3 ) + ( t << 1 ) + ch - '0';
}while ( ( ch = getchar() ) != EOF );
}
int main()
{
int cases, i, uu, vv, ww;
IIL ans;
//scanf( "%d", &cases );
cases = GetInt();
while ( cases-- )
{
memset( g, -1, sizeof( g ) );
//scanf( "%d%d", &v, &e );
v = GetInt(); e = GetInt();
for ( i = 0; i < v; ++i )
weight[i] = GetInt();
//scanf( "%d", &weight[i] );
for ( p = i = 0; i < e; ++i )
{
//scanf( "%d%d%d", &uu, &vv, &ww );
uu = GetInt(); vv = GetInt(); ww = GetInt();
addEdge( uu-1, vv-1, ww );
addEdge( vv-1, uu-1, ww );
}
if ( v == 0 || v == 1 )
{
printf( "0\n" );
continue;
}
SPFA( 0, v );
for ( ans = 0, i = 0; i < v; ++i )
{
if ( dist[i] == NIL ) break;
ans += dist[i]*weight[i];
}
if ( i == v )
printf( "%lld\n", ans );
else
printf( "No Answer\n" );
}
return 0;
}
pku 2446 Chessboard
二分匹配：构图很简单，注意构图的时候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;
}
poj 1275 Cashier Employment
差分约束系统(SPFA)
对于差分约束系统，建立的不等式是>=则在SPFA中求最长路。A-B>=C，则从B连一条权为C的边到A。
反之求最短路。A-B<=C，则从B连一条权为C的边到A。
注意两者对DIS初始化的不同
具体分析见2006国家集训队论文冯威--数与图的完美结合---浅析差分约束系统
#include <stdio.h>
#include <string.h>
#define MAXN 30
#define MAXE 100
#define INF 0x3fffffff
struct node
{
int v, d, next; //
}pot[MAXE];
int g[MAXN], pl, r[MAXN], t[MAXN], c[MAXN];
int dis[MAXN], visit[MAXN], queue[MAXN], ans;
int spfa( int n, int s ) //点的个数，源点，汇点
{
int top, tail, u, v, k;
for ( u = 1; u <= 24; ++u )
dis[u] = -INF;
memset( visit, 0, sizeof( visit ) );
memset( c, 0, sizeof( c ) );
dis[s] = 0; top = 0; tail = 1;
queue[0] = s; visit[s] = 1;
while ( top != tail ) //循环队列
{
u = queue[top++]; visit[u] = 0;
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;
if ( ++c[v] > n ) return 0;
if ( ++tail == n ) tail = 0;
}
}
}
}
return ( dis[24] == ans );
}
void addEdge( int u, int v, int w )
{
pot[pl].next = g[u];
pot[pl].v = v; pot[pl].d = w;
g[u] = pl++;
}
void ConstructGraph()
{
int i;
memset( g, -1, sizeof( g ) );
pl = 0;
for ( i = 1; i <= 16; ++i )
addEdge( i, i+8, r[i+8] );
for ( i = 1; i <= 8; ++i )
addEdge( i+16, i, r[i]-ans );
for ( i = 1; i <= 24; ++i )
addEdge( i-1, i, 0 );
for ( i = 1; i <= 24; ++i )
addEdge( i, i-1, -t[i] );
//这句感觉应该是addEdge( 24, 0, -ans )，即S24-S0<=ans，但是错了，也许题目中“Note that there can be
//more cashiers than the least number needed for a specific slot. ”是一个提醒吧。。。
addEdge( 0, 24, ans );
}
int main()
{
int cases, m, i, x;
scanf( "%d", &cases );
while ( cases-- )
{
memset( t, 0, sizeof( t ) );
for ( i = 1; i <= 24; ++i )
scanf( "%d", &r[i] );
scanf( "%d", &m );
for ( i = 0; i < m; ++i )
{
scanf( "%d", &x );
t[x+1]++;
}
for ( ans = 0; ans <= m; ++ans )
{
ConstructGraph();
if ( spfa( 25, 0 ) ) break;
}
if ( ans <= m )
printf( "%d\n", ans );
else
printf( "No Solution\n");
}
return 0;
}
pku 1201 Intervals
题目意思：给一些整数区间[x,y]，要求找一个元素个数最小的集合s，使得每个区间在集合s中都有z个元素。
分析一：贪心，将区间[x,y]按照从大到小排列，取尽可能前面的z个元素。结果悲剧TLE。
#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;
}
POJ 2516 Minimum Cost
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;
}