题目:http://poj.org/problem?id=3680
还是建图的问题。
离散化+最小费用流。
推荐博文:http://hi.baidu.com/juner_king/blog/item/a6b7cc822cba01dd9023d933.html
源代码:(用时:547ms)
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; typedef int typef; typedef int typec; const int N = 405, M = 2000; const typef inff = 0x3f3f3f3f; const typec infc = 0x3f3f3f3f; int a[N],b[N]; int l[N],r[N],w[N]; int x,n,k,cas; struct MinCostMaxFlow { int e, ev[M], nxt[M], head[N]; typec cost[M], dist[N]; typef cap[M]; int pnt[N], road[N], q[N], bg, ed; bool vis[N]; void init() { e = 0; memset(head,-1,sizeof(head)); } void addedge(int u, int v, typef f, typec c) { //u->v flow=f, cost=c ev[e]=v; cap[e]=f; cost[e]=c; nxt[e]=head[u]; head[u]=e++; ev[e]=u; cap[e]=0; cost[e]=-c; nxt[e]=head[v]; head[v]=e++; } bool spfa(int s, int t, int n) { for(int i=0;i<=n;i++) dist[i] = infc, vis[i] = 0; bg = ed = dist[s] = 0; pnt[s] = s; q[ed++] = s; while (bg != ed) { int u = q[bg++]; vis[u] = 0; if (bg == N) bg = 0; for (int i = head[u]; ~i; i = nxt[i]) { if (cap[i] <= 0)continue; int v = ev[i]; if (dist[v] > dist[u] + cost[i]) { dist[v] = dist[u] + cost[i]; pnt[v] = u; road[v] = i; if (!vis[v]) { q[ed++] = v; vis[v] = 1; if(ed == N)ed = 0; } } } } return dist[t] != infc; } void mincost(int s, int t, int n, typef &f, typec &c) { c = f = 0; while(spfa(s, t, n)){ typef minf = inff; for(int u = t; u != s; u = pnt[u]) minf = min(minf, cap[road[u]]); for(int u = t; u != s; u = pnt[u]){ cap[road[u]] -= minf; cap[road[u] ^ 1] += minf; } f += minf; c += minf * dist[t]; } } }; int solve() { int xx,ll,rr; int ans1,ans; MinCostMaxFlow tmp; sort(a,a+x); xx=0; b[xx++]=a[0]; for(int i=1;i<x;i++) if(a[i]!=a[i-1]) b[xx++]=a[i]; tmp.init(); for(int i=1;i<=xx+1;i++) tmp.addedge(i-1,i,k,0); for(int i=1;i<=n;i++) { for(int j=0;j<xx;j++) { if(b[j]==l[i]) ll=j+1; if(b[j]==r[i]) rr=j+1; } tmp.addedge(ll,rr,1,-w[i]); } tmp.mincost(0,xx+1,xx+2,ans1,ans); return -ans; } int main() { //freopen("F:\\a.txt","r",stdin); scanf("%d",&cas); while(cas--) { scanf("%d %d",&n,&k); x=0; for(int i=1;i<=n;i++) { scanf("%d %d %d",&l[i],&r[i],&w[i]); a[x++]=l[i]; a[x++]=r[i]; } printf("%d\n",solve()); } }