1035 火车停留 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master
题目描述 Description “今天你要去远行，送你风雨中…..”，伴着凄美的歌声，郭靖夫妇终于踏上征程。为了尽快到达边疆为国效力，他们搭上了2002次列车。可在途径sweet station时，被该站站长缠住了身，是什么原因呢？ 因为该车站由于经营不善，面临破产，该站负责人早闻黄蓉聪明过人，一定要她帮忙出出主意，挽救车站。 该车站有n个车道，由于车道的长度有限，每个车道在某一时刻最多只能停靠一列火车。该站每天将有m列火车从车站经过，其中第i列火车到达车站的时间为Reach[i]，火车上装有价值Cost[i]的货物。 如果该火车进站，则车站将获得Cost[i]的1%收益，但由于货物的搬运时间，该火车将在车站停留一段时间Stay[i]，这段时间内，火车将占用车站中的某一个车道。当然，火车也可以不在站中停靠而直接出站，但这样车站将得不到一分钱。 要挽救车站，就是要对车站的列车进行调度，使获得的效益最大。当然，解决这个问题对于黄蓉来说并不难，但边疆吃紧，时间不等人，你能帮帮黄蓉，让她脱身吗？ 任务:运行你的程序得到该站的最大效益。
输入描述 Input Description 第1行中为两个正整数：n（n≤20）m（m≤100），第2行到第m+1行，每行有3个不超过1000正整数。第i+1行的3个数分别为：Reach[i]， Cost[i]和Stay[i]，它们用单个空格分隔。
输出描述 Output Description 仅有一行，为车站的最大收益（精确到小数点后2位）。注意，如果火车a从第i车道离开时，火车b刚好到站（即Reach[a]+Stay[a] =Reach[b]），则它不能进入第i车道。
样例输入 Sample Input 1 3 2 5 1 3 4 1 5 6 2
样例输出 Sample Output 0.11
把每辆火车拆成两个点中间连边容量为1，费用为cost[i]，然后把所有满足 i 的结束时间早于 j 的开始时间的连边 i’->j 容量为1，费用为0，然后求最大费用流即可。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> using namespace std; const int maxn=100; struct Edge { int to,next; int cap,cost; }edge[maxn*maxn<<2]; int maxedge=-1; int head[maxn<<2]; inline void addedge(int u,int v,int cap,int cost) { edge[++maxedge]=(Edge){v,head[u],cap,cost}; head[u]=maxedge; edge[++maxedge]=(Edge){u,head[v],0,-cost}; head[v]=maxedge; } struct Train { int t1,t2; }train[maxn+5]; int n,m,maxnode; int S,T,s0,t0; inline void init() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); int reach,cost,stay; S=(m<<1)+1,s0=S+1,t0=s0+1,T=t0+1;maxnode=2*m+4; addedge(S,s0,n,0);addedge(t0,T,n,0); for(int i=1;i<=m;i++) { scanf("%d%d%d",&reach,&cost,&stay); train[i]=(Train){reach,stay+reach}; addedge(s0,i,1,0);addedge(i+m,t0,1,0); addedge(i,i+m,1,-cost); } for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) { if(i==j) continue; if(train[i].t2<train[j].t1) addedge(i+m,j,1,0); } } bool inque[maxn<<2]; int dis[maxn<<2],add[maxn<<2],pre[maxn<<2],edge_pre[maxn<<2]; inline bool spfa() { deque <int> que; memset(inque,false,sizeof(inque)); memset(dis,0x3f,sizeof(dis)); add[S]=0x3f3f3f3f;inque[S]=true;dis[S]=0;que.push_back(S); while(!que.empty()) { int u=que.front();que.pop_front();inque[u]=false; for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap&&dis[v]>dis[u]+edge[i].cost)//must judge if the cap { dis[v]=dis[u]+edge[i].cost; add[v]=min(add[u],edge[i].cap); pre[v]=u;edge_pre[v]=i; if(inque[v]) continue; inque[v]=true; if(que.empty()||dis[v]<dis[que.front()]) if(!que.empty()) que.push_front(v); else que.push_back(v); else que.push_back(v); } } } if(dis[T]>=0x3f3f3f3f) return false;//the = needed to be taken! return true; } inline int MCMF() { int flow=0,cost=0; while(spfa()) { flow+=add[T]; cost+=add[T]*dis[T]; for(int i=T;i!=S;i=pre[i]) { int e=edge_pre[i]; edge[e].cap-=add[T];edge[e^1].cap+=add[T]; } } return cost; } int main() { freopen("train.in","r",stdin); freopen("train.out","w",stdout); init(); printf("%.2lf\n",(double)-MCMF()/100); return 0; }