bzoj1221 [HNOI2001]软件开发 bzoj3280 小R的烦恼

bzoj1221 [HNOI2001]软件开发 & bzoj3280 小R的烦恼

bzoj1221 [HNOI2001]软件开发

Description
某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。

Input
第1行为n,a,b,f,fA,fB. 第2行为n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）

Output
最少费用

Sample Input
4 1 2 3 2 1
8 2 1 6

Sample Output
38

bzoj3280 小R的烦恼

Description
小R最近遇上了大麻烦，他的程序设计挂科了。于是他只好找程设老师求情。善良的程设老师答应不挂他，但是要求小R帮助他一起解决一个难题。
问题是这样的，程设老师最近要进行一项邪恶的实验来证明P=NP，这个实验一共持续n天，第i天需要a[i]个研究生来给他搬砖。研究生毕竟也是人，所以雇佣研究生是需要钱的，机智的程设老师已经联系好了m所大学，第j所大学共有l[j]个研究生，同时雇佣这所大学的一个研究生需要p[j]元钱。
本来程设老师满心欢喜的以为，这样捡最便宜的max{a[i]}个研究生雇来，就可以完成实验；结果没想到，由于他要求硕士生们每天工作25个小时不许吃饭睡觉上厕所喝水说话咳嗽打喷嚏呼吸空气，因此一天下来给他搬砖的所有研究生都会进入濒死状态。濒死状态的研究生，毫无疑问，就不能再进行工作了。但是机智的老师早早联系好了k家医院，第i家医院医治一个濒死的研究生需要d[i]天,并且需要q[i]元钱。
现在，程设老师想要知道，最少花多少钱，能够在这n天中满足每天的需要呢？若无法满足，则请输出”impossible”。注意，由于程设老师良心大大的坏，所以他是可以不把濒死的研究生送去医院的！

Input
本题包含多组数据；第一行是一个数T(T<=11)，表示数据组数，以下T组数据。
对于每一组数据，第一行三个数，n,m,k;
以下一行n个数，表示a[1]…a[n]
接着一行2m个数，表示l[1],p[1]…l[n],p[n]
接着一行2k个数，表示d[1],q[1]…d[n],q[n]

Output
对于每组数据以样例的格式输出一行，两个数分别表示第几组数据和最少钱数。

Sample Input
2
3 2 1
10 20 30
40 90 15 100
1 5
3 2 1
10 20 30
40 90 15 100
2 5

Sample Output
Case 1: 4650
Case 2: impossible

HINT
样例解释：买下90块钱的那40个研究生，另外再买10个100块钱的。这样，第一天用完的10个人全部送到医院，那么他们在第三天可以继续使用；同时，第二天和第三天都用新的研究生来弥补，这样一共需要花费40*90 + 10*100 + 5*10 = 4650元。

数据规模：
对于30%的数据中的每组数据,
满足n<=5,m,k<=2,其余数均小于等于100或者
n<=10,m,k<=10,其余数均小于等于20.
对于100%的数据
n,m,k<=50,其余数均小于等于100.

为什么把这两题放在一起呢？因为他们很像啊.. 强行解释自己不想写多一篇博客

好吧其实真的很像，特别是这个构图非常经典.. 那么我就以1221为例吧.. 因为两个构图基本相同..

首先定义2*n个点，这2*n个点我把它分成两类，每一类都有n个点..
X类点中第i个点表示第i天有多少餐巾用过，需要清洗，用当天可以用脏的餐巾数限制(st,i,a[i],0)
Y类点中第i个点表示第i天所拥有的干净餐巾数，用当天可以用脏的餐巾数限制(i+n,ed,a[i],0)
那么第i天的干净餐巾可以留到i+1天使用(i+n,i+n+1,inf,0)
我可以第一天买我接下来所有天所需要买的干净餐巾(st,1+n,inf,f)
然后第i天用脏的餐巾经过洗涤可以在i+aa+1天以后使用(i,i+aa+1+n,inf,fa)
当然第i天用脏的餐巾经过洗涤也可以在i+bb+1天使用(i,i+bb+1+n,fb)

就是这么构图.. 我觉得我讲的还是比较清晰的吧.. 不好的请老司机来指点..

我不会告诉你当初1221是抄题解的.. 什么也不会啊 那么3280也是同样的构图方法..

code
只有3280的.. 你问我为什么？我上面不是说了嘛..

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int Maxn = 110;
const int inf = 0x7fffffff;
struct node {int x, y, next, c, d, opp;
}a[Maxn*Maxn*10]; int first[Maxn], len;
int _min ( int x, int y ){ return x < y ? x : y; }
void ins ( int x, int y, int c, int d ){len ++; int k1 = len;a[len].x = x; a[len].y = y; a[len].c = c; a[len].d = d;a[len].next = first[x]; first[x] = len;len ++; int k2 = len;a[len].x = y; a[len].y = x; a[len].c = 0; a[len].d = -d;a[len].next = first[y]; first[y] = len;a[k1].opp = k2;a[k2].opp = k1;
}
int st, ed, sc;
int n, m, K;
int dis[Maxn], pre[Maxn];
bool mark[Maxn];
bool bfs (){queue <int> q;memset ( pre, -1, sizeof (pre) );memset ( dis, 63, sizeof (dis) );memset ( mark, false, sizeof (mark) );q.push (st); dis[st] = 0; mark[st] = true;while ( !q.empty () ){int x = q.front (); q.pop ();for ( int k = first[x]; k; k = a[k].next ){int y = a[k].y;if ( dis[y] > dis[x]+a[k].d && a[k].c > 0 ){dis[y] = dis[x]+a[k].d;pre[y] = k;if ( mark[y] == false ){mark[y] = true;q.push (y);}}}mark[x] = false;} return pre[ed] > 0;
}
int dfs ( int x, int flow ){mark[x] = true;if ( x == ed ) return flow;int delta = 0;for ( int k = first[x]; k; k = a[k].next ){int y = a[k].y;if ( dis[y] == dis[x]+a[k].d && a[k].c > 0 && flow-delta > 0 && mark[y] == false ){int minf = dfs ( y, _min ( a[k].c, flow-delta ) );sc += minf*a[k].d;delta += minf;a[k].c -= minf;a[a[k].opp].c += minf;}}return delta;
}
int main (){int i, j, k, T, Ti;Ti = 0;scanf ( "%d", &T );while ( T -- ){scanf ( "%d%d%d", &n, &m, &K );len = 0; memset ( first, 0, sizeof (first) );st = 0; ed = 2*n+1;int sum = 0;for ( i = 1; i <= n; i ++ ){int x;scanf ( "%d", &x );ins ( st, i, x, 0 );ins ( i+n, ed, x, 0 );sum += x;}for ( i = 1; i <= m; i ++ ){int x, y;scanf ( "%d%d", &x, &y );ins ( st, 1+n, x, y );}for ( i = 1; i < n; i ++ ) ins ( i+n, i+n+1, inf, 0 );for ( i = 1; i <= K; i ++ ){int x, y;scanf ( "%d%d", &x, &y );for ( j = 1; j <= n-x-1; j ++ ){ins ( j, j+x+1+n, inf, y );}}int ans = 0;sc = 0;while ( bfs () ){mark[ed] = true;while ( mark[ed] ){memset ( mark, false, sizeof (mark) );ans += dfs ( st, inf );} }printf ( "Case %d: ", ++Ti );if ( ans != sum ) printf ( "impossible\n" );else printf ( "%d\n", sc );}return 0;
}

啊啊啊我漏了个换行符让我整整等了1min的评测啊.. bzoj评测差评..