poj 3680 Intervals 费用流
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=1e3+9,inf=1e8;int from[maxn],to[maxn],w[maxn],x[maxn];int head[maxn],lon;int dist[maxn],inque[maxn],que[1111111];int T,n,K;struct{ int next,to,c,w,from;}e[maxn*maxn];void edgeini(){ memset(head,-1,sizeof(head)); lon=-1;}void edgemake(int from,int to,int c,int w){ e[++lon].to=to; e[lon].c=c; e[lon].w=w; e[lon].from=from; e[lon].next=head[from]; head[from]=lon;}bool spfa(){ memset(dist,200,sizeof(dist)); memset(inque,0,sizeof(inque)); memset(from,-1,sizeof(from)); int front=1,end=0; dist[0]=0; inque[0]=1; que[++end]=0; while(front<=end) { int t=que[front++]; inque[t]=0;// if(t==n+n+1) return true; for(int k=head[t];k!=-1;k=e[k].next) { if(e[k].c<=0) continue; int u=e[k].to,w=e[k].w; if(dist[u]<dist[t]+w) { dist[u]=dist[t]+w; from[u]=k; if(!inque[u]) { inque[u]=1; que[++end]=u; } } } } return from[n+n+1]!=-1;}int maxflow(){ int ans=0;// for(int i=1;i<=K;i++) { while(spfa()) for(int u=from[n+n+1];u!=-1;u=from[e[u].from]) { e[u].c--; e[u^1].c++; ans+=e[u].w; } } return ans;}int main(){// freopen("in.txt","r",stdin); scanf("%d",&T); int tt=0; while(T--) { edgeini(); scanf("%d %d",&n,&K); for(int i=1;i<=n;i++) { scanf("%d%d%d",&from[i],&to[i],&w[i]); x[i*2]=from[i]; x[i*2-1]=to[i]; } sort(x+1,x+1+n+n); for(int i=2;i<=n+n;i++) if(x[i]==x[i-1]) x[i-1]=1111111; sort(x+1,x+1+n+n); for(int i=1;i<=n+n;i++) { edgemake(i,i+1,inf,0); edgemake(i+1,i,0,0); } for(int i=1;i<=n;i++) { int s=lower_bound(x+1,x+n+n,from[i])-x; int t=lower_bound(x+1,x+n+n,to[i])-x; if(s>t) swap(s,t); edgemake(s,t,1,w[i]); edgemake(t,s,0,-w[i]); } edgemake(0,1,K,0); edgemake(1,0,0,0); int ans=maxflow();// if(++tt!=1) cout<<endl; cout<<ans<<endl; } return 0;}