点击打开链接
题意：给n个区间，每一个区间可以同时工作k个工作，问这n个工作的最大利润
思路：挑战程序设计上的例题，大神解释的已经很清楚了，不多说了，主要考察的就是建图
#include <queue> #include <vector> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3fll; const int maxn=810; typedef pair<int,int> P; struct edge{ int to,cap,rev,cost; edge(); edge(int a,int b,int c,int d){to=a,cap=b,cost=c,rev=d;}; }; vector<edge>G[maxn]; int h[maxn],dis[maxn]; int prevv[maxn],preve[maxn]; void addedge(int st,int en,int cap,int cost){ G[st].push_back(edge(en,cap,cost,G[en].size())); G[en].push_back(edge(st,0,-cost,G[st].size()-1)); } int min_cost_flow(int st,int en,int f){ int ans=0; memset(h,0,sizeof(h)); while(f>0){ priority_queue<P,vector<P>,greater<P> >que; for(int i=0;i<maxn;i++) dis[i]=inf; dis[st]=0;que.push(P(0,st)); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(dis[v]<p.first) continue; for(unsigned int i=0;i<G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&dis[e.to]>dis[v]+e.cost+h[v]-h[e.to]){ dis[e.to]=dis[v]+e.cost+h[v]-h[e.to]; prevv[e.to]=v; preve[e.to]=i; que.push(P(dis[e.to],e.to)); } } } if(dis[en]==inf) return -1; for(int i=0;i<maxn;i++) h[i]+=dis[i]; int d=f; for(int i=en;i!=st;i=prevv[i]){ d=min(d,G[prevv[i]][preve[i]].cap); } f-=d; ans+=d*h[en]; for(int i=en;i!=st;i=prevv[i]){ edge &e=G[prevv[i]][preve[i]]; e.cap-=d; G[i][e.rev].cap+=d; } } return ans; } int A[maxn],B[maxn],C[maxn],tmp[maxn]; int main(){ int T,n,m; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=0;i<maxn;i++) G[i].clear(); int len=0; for(int i=0;i<n;i++) scanf("%d%d%d",&A[i],&B[i],&C[i]),tmp[len++]=A[i],tmp[len++]=B[i]; sort(tmp,tmp+len); int kkk=1; for(int i=1;i<len;i++) if(tmp[i]!=tmp[i-1]) tmp[kkk++]=tmp[i]; int ans=0; addedge(0,1,m,0);addedge(kkk,kkk+1,m,0); for(int i=1;i<kkk;i++) addedge(i,i+1,inf,0); for(int i=0;i<n;i++){ int a=lower_bound(tmp,tmp+kkk,A[i])-tmp+1; int b=lower_bound(tmp,tmp+kkk,B[i])-tmp+1; addedge(b,a,1,C[i]); addedge(0,b,1,0); addedge(a,kkk+1,1,0); ans-=C[i]; } ans+=min_cost_flow(0,kkk+1,m+n); printf("%d\n",-ans); } return 0; }