这是我在codeforces上做的第一个网络流的题目，思维还不错，讲讲
题意：给你n个任务，k个机器，n个任务的起始时间，持续时间，完成任务的获利
每个机器可以完成任何一项任务，但是同一时刻只能完成一项任务，一旦某台机器在完成某项任务时，直到任务结束，这台机器都不能去做其他任务
最后问你当获利最大时，应该安排那些机器工作，即输出方案
刚看到题就想到一个贪心的思路，如果一台机器完成了某项工作，它应该继续去完成接下来最先开始的工作，感觉有点像网络流里面的建图啊，于是继续往这个方向YY，
我擦，结果还真可以网络流来搞。
具体建图方法：
新建源汇S T‘
对任务按照起始时间s按升序排序
拆点：
u 向 u'连一条边 容量为 1 费用为 -c,
u' 向 T连一条边 容量为 inf 费用为 0；
如果任务u完成后接下来最先开始的是任务v
则从u' 向 v连一条边，容量inf 费用 0.
另外，任务从前往后具有传递性，所以必须是第i个任务向第i+1个任务建边，容量为inf
最后，限制一下起始点向第一个任务的流量即可（即K）
my code
View Code
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int Sum_Flow; const int N = 3000; const int M = 100000; const int inf = ~0u>>2; struct Edge{ int u,v,cap,cost; int next; }edge[M]; int E; int head[N],dist[N],pre[N]; bool vis[N]; void init() { E=0; memset(head,-1,sizeof(head)); } void add_edge(int u,int v,int cap,int cost) { edge[E].u=u;edge[E].v=v;edge[E].cap=cap;edge[E].cost=cost; edge[E].next=head[u];head[u]=E++; edge[E].u=v;edge[E].v=u;edge[E].cap=0;edge[E].cost=-cost; edge[E].next=head[v];head[v]=E++; } bool spfa(int s,int t,int n) { queue<int> Q; fill(vis,vis+n+1,false); fill(pre,pre+n+1,-1); fill(dist,dist+n+1,inf); vis[s]=true;dist[s]=0; Q.push(s); while(!Q.empty()) { int u=Q.front();Q.pop();vis[u]=false; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(edge[i].cap && dist[v] > dist[u]+ edge[i].cost) { dist[v] = dist[u]+edge[i].cost; pre[v]=i; if(!vis[v]) { Q.push(v); vis[v]=true; } } } } if(dist[t] == inf) return false; return true; } int MCMF(int s,int t,int n) { int flow=0; int minflow,mincost=0; while(spfa(s,t,n)) { minflow=inf+1; for(int i=pre[t];i!=-1;i=pre[edge[i].u]) if(edge[i].cap < minflow) minflow=edge[i].cap; flow+=minflow; for(int i=pre[t];i!=-1;i=pre[edge[i].u]) { edge[i].cap-=minflow; edge[i^1].cap+=minflow; } mincost += dist[t] * minflow; } Sum_Flow = flow; return mincost; } struct node{ int s,t,c; int id; }in[N]; int ans[N]; int cmp(node a, node b){ return a.s<b.s; } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { init(); int S = 2*n,T = 2*n+1; for(int i=0;i<n;i++){ scanf("%d%d%d",&in[i].s,&in[i].t,&in[i].c); in[i].t=in[i].s+in[i].t-1; in[i].id=i; } sort(in,in+n,cmp); for(int i=0;i<n;i++) { add_edge(i,i+n,1,-in[i].c); add_edge(i+n,T,inf,0); if(i<n-1) add_edge(i,i+1,inf,0); for(int j=i+1;j<n;j++) { if(in[i].t<in[j].s) { add_edge(i+n,j,inf,0); break; } } } add_edge(S,0,k,0); add_edge(n-1,T,k,0); MCMF(S,T,T+1); memset(ans,0,sizeof(ans)); for(int i=0;i<E;i+=2) { if(!edge[i].cap) { int u=edge[i].u,v=edge[i].v; if(u!=S && u!=T && u<n) { ans[in[u].id]=1; } } } for(int i=0;i<n;i++) printf("%d ",ans[i]); puts(""); } return 0; }