[HDU6118][2017"百度之星"程序设计大赛 - 初赛（B）]度度熊的交易计划

Problem Description

度度熊参与了喵哈哈村的商业大会，但是这次商业大会遇到了一个难题：喵哈哈村以及周围的村庄可以看做是一共由n个片区，m条公路组成的地区。由于生产能力的区别，第i个片区能够花费a[i]元生产1个商品，但是最多生产b[i]个。同样的，由于每个片区的购买能力的区别，第i个片区也能够以c[i]的价格出售最多d[i]个物品。由于这些因素，度度熊觉得只有合理的调动物品，才能获得最大的利益。据测算，每一个商品运输1公里，将会花费1元。那么喵哈哈村最多能够实现多少盈利呢？

Input

本题包含若干组测试数据。

每组测试数据包含：

第一行两个整数n,m表示喵哈哈村由n个片区、m条街道。

接下来n行，每行四个整数a[i],b[i],c[i],d[i]表示的第i个地区，能够以a[i]的价格生产，最多生产b[i]个，以c[i]的价格出售，最多出售d[i]个。

接下来m行，每行三个整数,u[i],v[i],k[i]，表示该条公路连接u[i],v[i]两个片区，距离为k[i]

可能存在重边，也可能存在自环。

满足:

1<=n<=500,

1<=m<=1000,

1<=a[i],b[i],c[i],d[i],k[i]<=1000,

1<=u[i],v[i]<=n

Output

输出最多能赚多少钱。

Sample Input

   
   

    
    

     
     2 1
    
    
   
   

   
   

    
    

     
     5 5 6 1
    
    
   
   

   
   

    
    3 5 7 7
   
   

   
   

    
    

     
     1 2 1
    
    
   
   

Sample Output

23

题解：费用流裸题。

因为算的是支出，最后答案要取反。

思路不难，重在细心和代码实现能力。

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

const int INF=0x3f3f3f3f;
const int T=505;
const int N=1010;
const int M=T*T;


int n, m, fir[N], ecnt, map[T][T];
struct nodes{ int e, cap, cost, next; }edge[M];
void Link( int s, int e, int cost, int cap ) {
	edge[++ecnt].e=e; edge[ecnt].next=fir[s]; fir[s]=ecnt;
	edge[ecnt].cost=cost; edge[ecnt].cap=cap;
	edge[++ecnt].e=s; edge[ecnt].next=fir[e]; fir[e]=ecnt;
	edge[ecnt].cost=-cost; edge[ecnt].cap=0;
}

void Build() {
	for( int i=1; i<=n; i++ ) {
		int a, b, c, d;
		scanf( "%d%d", &a, &b );
		scanf( "%d%d", &c, &d );
		Link( 1, i+1, a, b );
		Link( i+1, i+n+1, 0, INF);//此处是拆点的连法, 也可以选择不拆点
		Link( i+n+1, n*2+2, -c, d );
	}
	for( int i=1; i<=m; i++ ) {
		int s, e, w;
		scanf( "%d%d%d", &s, &e, &w );
		Link( e+n+1, s+1, w, INF );
		Link( s+n+1, e+1, w, INF );
	}
	n=n*2+2;
}

queue<int> q;
int dis[N];
bool used[N];
bool Spfa() {
	q.push(n);
	memset( dis, INF, sizeof dis );  dis[n]=0;
	while( !q.empty() ) {
		int s=q.front(); used[s]=0; q.pop();
		for( int i=fir[s]; i; i=edge[i].next )
			if( edge[i^1].cap>0 )
				if( dis[ edge[i].e ]>dis[s]+edge[i^1].cost ) {
					dis[ edge[i].e ]=dis[s]+edge[i^1].cost;
					if( !used[ edge[i].e ] )
						q.push( edge[i].e ), used[ edge[i].e ]=1;
				}
	}
	if( dis[1]>0 ) return 0;
	return 1;
}


int sum;
bool vis[N];
int minCost( int s, int max_aug ) {
	if( s==n ) {
		sum+=dis[1]*max_aug; return max_aug;
	}
	int rest_aug=max_aug, delta;
	for( int i=fir[s]; i && rest_aug>0; i=edge[i].next )
		if( !vis[ edge[i].e ] && edge[i].cap>0 )
			if( dis[s]==dis[ edge[i].e ]+edge[i].cost ) {
				vis[ edge[i].e ]=1;
				delta=minCost( edge[i].e, min( rest_aug, edge[i].cap ) );
				edge[i].cap-=delta;
				edge[i^1].cap+=delta;
				rest_aug-=delta;
			}
	return max_aug-rest_aug;
}

void Reset() {
	sum=0;  ecnt=1;
	memset( fir, 0, sizeof fir );
	memset( used, 0, sizeof used );
}

int main() {
	while( ~scanf( "%d%d", &n, &m ) ) {
		Reset();
		Build();
		while( Spfa() ) { 
			memset( vis, 0, sizeof vis ); 
			minCost( 1, INF );
		}
		printf( "%d\n", -sum );
	}
	return 0;
}