学步园

YM BROTHER SHI的题

只需要添加 (T, S, MID, INF) , 作为新图并跑一次 无源汇的可行流,找到最大的MID 可行，那么MID就是最大流
同时对于残留网络统计得到信息，一开始以为所有MM都要输出于是杯具了……

【程序代码】

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 1505, maxm = 100005, inf = 0x3f3f3f3f;
int head[maxn],l,next[maxm],vpt[maxm],flow[maxm],low[maxm];
int vh[maxn],d[maxn],pre[maxn],preh[maxn],now[maxn];
typedef pair<int,int> PII;
#define mp make_pair
void init(){
l = 1;
memset(head, 0, sizeof head);
memset(d,0 , sizeof d);
} 

void add(int a,int b,int c,int lo){
vpt[++l]=b;next[l]=head[a];head[a]=l;flow[l]=c;low[l]=lo;
vpt[++l]=a;next[l]=head[b];head[b]=l;flow[l]=0;low[l]=lo;
}
int sap(int n,int s,int t){
int i,k,f,x,y,ans = 0;
for(i = 0; i < n; ++ i) now[i] = head[i];
vh[0] = n; x = s;
while(d[s] < n){
if(x == t){
for(f = inf, i = t; i ^ s; i = pre[i]) f = min(f, flow[preh[i]] ) ;ans += f;
for(i = t; i ^ s; i = pre[i]) flow[ preh[i]] -= f, flow[preh[i] ^ 1] += f; x = s;
}
for( i =now[x]; i; i = next[i]) if(flow[i] > 0 && d[y = vpt[i]] + 1 == d[x]) {now[x] = i; break;}
if(i) pre[y] = x, preh[y] = i, x = y; else{
if(!--vh[d[x]]) break; k = n;
for(i = now[x] = head[x]; i; i =next[i]) if(flow[i] > 0 && k > d[vpt[i]]) now[x] =i, k = d[vpt[i]];
++ vh[d[x] = k + 1]; if(x ^ s) x = pre[x];
}
}
return ans;
}

int n, m ;
pair< vector < pair<int, PII > > , int> Day[maxn]; 
int Gx[maxn];
int D[maxn] ;
int Tot; 
bool ok(int mid){ //check if the available flow exist...
if(mid < 0) return 0 ;
int s = 0, t = n + m + 1, SS = t + 1, TT = SS + 1;
int i,j,k;
init() ;
memset(D, 0, sizeof D) ;
for(i = 1; i <= n; ++ i){
add(s, i, Day[i].second,0) ; //[0, Day[i].second] ...
for(j = 0; j < Day[i].first.size(); ++ j) {
int T, L, R;
T = Day[i].first[j].first; L = Day[i].first[j].second.first; R = Day[i].first[j].second.second;
add(i, T + n, R - L,L) ; //[L, R] ...
D[i] -= L; D[T + n] += L ;
}
}
for(i = 1; i <= m; ++ i) add(i + n, t, inf - Gx[i],Gx[i]), D[i + n] -= Gx[i], D[t] += Gx[i] ; //[Gx,inf) ...
add(t, s, inf-mid, mid) ;
D[t] -= mid; D[s] += mid;
for(i = 0; i <= t; ++ i) if(D[i])
if(D[i] > 0) add(SS, i, D[i],0) ;else add(i, TT, - D[i],0) ;
bool flg = 1;
int fl = sap(TT + 1, SS, TT) ;
for(i = head[SS]; i; i = next[i]) if(flow[i]) flg = 0;
for(i = head[TT]; i; i =next[i]) if(flow[i ^ 1]) flg = 0;
return flg ;
} 
bool get(){
if(EOF == scanf("%d%d",&n,&m)) return 0;
int i;
Tot = 0;
for(i = 1; i <= m; ++ i) scanf("%d",&Gx[i]) ;
for(i = 1; i <= n; ++ i){
Day[i].first.clear() ;
int sz ; scanf("%d",&sz);
scanf("%d",&Day[i].second);
Tot += Day[i].second ;
while(sz --){
int t, l, r;
scanf("%d%d%d",&t,&l,&r); ++ t; 
Day[i].first.push_back( mp(t, mp(l,r)));
}
}
return 1;
}
int Ans[maxn];

void work(){
int l, r, mid;
l = 0; r = Tot; mid = (l + r) >> 1;
while(l < r){
mid = (l + r ) >> 1;
if(ok(mid)) l = mid + 1;
else r = mid - 1;
}
int cnt = 0;
mid = min(Tot , mid + 1) ;
while( ! ok(mid) && cnt <= 3) -- mid, ++ cnt;
if(cnt > 3){
puts("-1");
puts("");
return; 
}
int i,j,k;
printf("%d\n", mid);
for(i = 1; i <= n; ++ i){
memset(Ans, - 1, sizeof Ans) ;
for(j = head[i]; j; j =next[j]) if(vpt[j] >= n + 1 && vpt[j] <= n + m) {
Ans[ vpt[j] - n] = low[j] + flow[j ^ 1] ;
}
for(j = 1; j <= m; ++ j)if(Ans[j] != - 1) 
printf("%d\n",Ans[j]);
}
puts("");
}
int main(){
while(get()) work(); 
return 0;
}
/*
Run ID Submit Time Judge Status Problem ID Language Run Time(ms) Run Memory(KB) User Name
2299910 2010-09-18 23:35:50 Accepted 3229 C++ 1400 2352 AekdyCoin
*/