2055: 80人环游世界
Time Limit: 10 Sec
Memory Limit: 64 MB
[
Submit][
Status][
Discuss]
Description
想必大家都看过成龙大哥的《80天环游世界》，里面的紧张刺激的打斗场面一定给你留下了深刻的印象。现在就有这么
一个80人的团伙，也想来一次环游世界。
他们打算兵分多路，游遍每一个国家。
因为他们主要分布在东方，所以他们只朝西方进军。设从东方到西方的每一个国家的编号依次为1...N。假若第i个人的游历路线为P1、P2......Pk(0≤k≤N)，则P1<P2<......<Pk。
众所周知，中国相当美丽，这样在环游世界时就有很多人经过中国。我们用一个正整数Vi来描述一个国家的吸引程度，Vi值越大表示该国家越有吸引力，同时也表示有且仅
有Vi个人会经过那一个国家。
为了节省时间，他们打算通过坐飞机来完成环游世界的任务。同时为了省钱，他们希望总的机票费最小。
明天就要出发了，可是有些人临阵脱逃，最终只剩下了M个人去环游世界。他们想知道最少的总费用，你能告诉他们吗？
Input
第一行两个正整数N，M。
第二行有N个不大于M正整数，分别表示V1，V2......VN。
接下来有N-1行。第i行有N-i个整数，该行的第j个数表示从第i个国家到第i+j个国家的机票费（如果该值等于-1则表示这两个国家间没有通航）。
Output
在第一行输出最少的总费用。
Sample Input
6 3 2 1 3 1 2 1 2 6 8 5 0 8 2 4 1 6 1 0 4 -1 4
Sample Output
27
HINT
1<= N < =100 1<= M <= 79
Source
上下界原图（很简单）
s->S m,m,0
S->xi 0,inf,0
yi->T 0,inf,0
xi->yi vi,vi,0
yi->xj 0,inf,ci
如何改造为上下界运行图
超超级源汇SS，TT
u->v x,y,ci 改为u->v y-x,ci
bi = 流入下界和-流出下界和
对于bi>0的点,SS->i,bi,0
bi<0的点,i->TT,bi,0
然后费用流
赶脚这个zkw费用流是错的，很多题都A不了
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x7fffffff
using namespace std;
const int N = 205;
int n,m,cnt=1,ans,S,T;
int last[N], b[N], q[N], d[N], inq[N], from[N];
struct Edge{
int to,v,next,c,from;
}e[N*N*5];
void insert( int u, int v, int w, int c ){
e[++cnt].to = v; e[cnt].c = c; e[cnt].v = w; e[cnt].next = last[u]; last[u] = cnt; e[cnt].from = u;
e[++cnt].to = u; e[cnt].c = -c; e[cnt].v = 0; e[cnt].next = last[v]; last[v] = cnt; e[cnt].from = v;
}/*
bool spfa(){
memset(inq,0,sizeof(inq));
for( int i = 0; i <= T; i++ ) d[i] = inf;
int head = 0, tail = 1;
inq[T] = 1; d[T] = 0; q[0] = T;
while( head != tail ){
int now = q[head++]; if( head == T ) head = 0;
for( int i = last[now]; i; i = e[i].next )
if( e[i^1].v && d[now]+e[i^1].c < d[e[i].to] ){
d[e[i].to] = d[now] + e[i^1].c;
if( !inq[e[i].to] ){
inq[e[i].to] = 1;
q[tail++] = e[i].to; if( tail == T ) tail = 0;
}
}
}
return d[S] != inf;
}
int dfs( int x, int f ){
inq[x] = 1;
if( x == T ) return f;
int w,used=0;
for( int i = last[x]; i; i = e[i].next )
if( d[e[i].to] == d[x]-e[i].c && e[i].v && !inq[e[i].to] ){
w = dfs( e[i].to, min(f-used,e[i].v) );
used += w; e[i].v -= w; e[i^1].v += w;
ans += e[i].c*w; if( used == f ) return f;
}
return used;
}
void zkw(){
while( spfa() ){
inq[T] = 1;
while( inq[T] ){
memset(inq,0,sizeof(inq));
dfs( S, inf );
}
}
}*/
bool spfa(){
for( int i = 0; i <= T; i++ ) d[i] = inf;
int head = 0, tail = 1;
d[0] = 0; q[0] = 0; inq[0] = 1;
while( head != tail ){
int now = q[head++]; if( head == T ) head = 0;
for( int i = last[now]; i; i = e[i].next )
if( e[i].v && e[i].c+d[now] < d[e[i].to] ){
d[e[i].to] = e[i].c+d[now]; from[e[i].to] = i;
if( !inq[e[i].to] ){
inq[e[i].to] = 1;
q[tail++] = e[i].to; if( tail == T ) tail = 0;
}
}
inq[now] = 0;
}
return d[T] != inf;
}
void mcf(){
int x=inf;
for( int i = from[T]; i; i = from[e[i].from] ) x=min(e[i].v,x);
for( int i = from[T]; i; i = from[e[i].from] ){
ans += x*e[i].c;
e[i].v -= x; e[i^1].v += x;
}
}
int main(){
scanf("%d%d", &n, &m); S = n*2+1; T = n*2+2;
for( int i = 1,x; i <= n; i++ ){
scanf("%d", &x);
insert( i, i+n, 0, 0 );
b[i] -= x; b[i+n] += x;
}
insert( 0, S, m, 0 );
for( int i = 1; i <= n; i++ ) insert( S, i, inf, 0 );
for( int i = 1; i <= n; i++ )
for( int j = i+1,x; j <= n; j++ ){
scanf("%d", &x);
if( x != -1 ) insert( i+n, j, inf, x );
}
for( int i = 1; i <= n*2; i++ ){
if( b[i] > 0 ) insert( 0, i, b[i], 0 );
if( b[i] < 0 ) insert( i, T, -b[i], 0 );
}
while(spfa()) mcf();
// zkw();
printf("%d", ans);
return 0;
}
