POJ 3680

建圖很巧妙

先離散化區間端點。從0->1,1->2,~~~~~n->n+1每條邊容量為k，費用為0，

對于每條線段，他的兩個端點連邊容量為1，費用-w

然後跑一遍最小費用流

算法正确性證明：

如果兩個區間沒有交集，那麼代表它們的邊可以出現在同一增廣路上，這一點顯然。否則，它們就在不同的增廣路上。每一個區間對應的邊的容量都是1，這樣，最後的流量就是被選出的兩兩有交集的區間的數量。受到(0,1,k,0)這條邊的容量限制，這個值剛好不大于k.區間的權都是正的，是以選取的區間多多益善，是以流量必然最大。

 （對于每次選取的增廣路中總存在一個區間，在每次增廣所得區間都與這個區間有交集）

#include<cstdio>
#include<stdlib.h>
#include<cstring>
using namespace std;
const int inf=99999999;
struct{
    int v, cap, cost, next, re;
}edge[2005];
struct{
	int a,b,w;
}line[210];
struct Li{
	int be,num;
}li[450];
int n,ans;
int k,edgeHead[500];
int que[500],pre[500],dis[500];
bool vis[500];
int cmp(const void * a,const void *b){  
    struct Li *aa=(struct Li *) a;  
    struct Li *bb=(struct Li *) b;  
	return aa->be-bb->be;  
}  

void addEdge(int u,int v,int ca,int co){
    edge[k].v=v;
    edge[k].cap=ca;
    edge[k].cost=co;
    edge[k].next=edgeHead[u];
    edge[k].re=k + 1;               //這個用來記錄此邊的反邊
    edgeHead[u]=k ++;
    edge[k].v=u;
    edge[k].cap=0;
    edge[k].cost=-co;               //故這裡去反費用（因為是反向邊）
    edge[k].next=edgeHead[v];
    edge[k].re=k - 1;
    edgeHead[v]=k ++;
}

bool spfa(){                //尋找最長增廣路時如果是正向邊則+相應的費用，反向邊-相應的費用
    int i, head = 0, tail = 1;    //  長注釋的地方就是從最小費用改到最大費用時需要變動的地方
    for(i = 0; i <= n; i ++){
        dis[i] = inf;
        vis[i] = false;
    }
    dis[0] = 0;
    que[0] = 0;
    vis[0] = true;
    while(head != tail){
        int u = que[head];
        for(i = edgeHead[u]; i != 0; i = edge[i].next){
            int v = edge[i].v;
            if(edge[i].cap && dis[v] >dis[u] + edge[i].cost){
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;                        // 這個pre數組記錄的是從邊号為i的那條邊去往v
                if(!vis[v]){
                    vis[v] = true;
                    que[tail ++] = v;
                    if(tail == 490) tail = 0;             // 這裡用到了循環隊列，節省空間
                }
            }
        }
        vis[u] = false;
        head++;
        if(head ==490) head = 0;
    }
    if(dis[n] ==inf) return false;///
    return true;
}

void end(){
    int u, p,mi;
	mi=inf;
	for(u = n; u != 0; u = edge[edge[p].re].v){
        p = pre[u];
        if(edge[p].cap<mi)
            mi=edge[p].cap;
    }
    for(u = n; u != 0; u = edge[edge[p].re].v){
        p = pre[u];
        edge[p].cap -= mi;
        edge[edge[p].re].cap += mi;
        ans += edge[p].cost*mi;
    }
}
int main(){
	int i,j,T,t,v,lim,a,b,w;
	scanf("%d",&T);
	for(t=1;t<=T;t++){
	    k=1;
		memset(edgeHead,0,sizeof(edgeHead));
		scanf("%d %d",&v,&lim);
		for(i=1;i<=v;i++){
			scanf("%d %d %d",&a,&b,&w);
			li[i*2-1].be=a;
			li[i*2-1].num=-i;
			li[i*2].be=b;
			li[i*2].num=i;

			line[i].a=a;
			line[i].b=b;
			line[i].w=w;
		}
		qsort(&li[1],2*v,sizeof(li[1]),cmp);
		int temp=li[1].be,tp=1;
		for(i=1;i<=v*2;i++){
			if(li[i].be!=temp){
				tp++;
				temp=li[i].be;
			}
			if(li[i].num>0) //注意這裡不能寫成if(li[i].num)因為大于0和小于0都滿足........在這裡T了無數次
				line[li[i].num].b=tp;
			else
				line[-li[i].num].a=tp;
		}
		for(i=0;i<=tp;i++){
			addEdge(i,i+1,lim,0);
		}
		n=tp+1;
		for(i=1;i<=v;i++){
			addEdge(line[i].a,line[i].b,1,-line[i].w);
		}
	    ans=0;
		while(spfa())end();
		printf("%d\n",-ans);
	}
    return 0;
}
           

用STL更簡捷

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=99999999;
struct{
    int v, cap, cost, next, re;
}edge[2005];
struct{
	int a,b,w;
}line[210];
int li[450];
int n,ans;
int k,edgeHead[500];
int que[500],pre[500],dis[500];
bool vis[500];

void addEdge(int u,int v,int ca,int co){
    edge[k].v=v;
    edge[k].cap=ca;
    edge[k].cost=co;
    edge[k].next=edgeHead[u];
    edge[k].re=k + 1;               //這個用來記錄此邊的反邊
    edgeHead[u]=k ++;
    edge[k].v=u;
    edge[k].cap=0;
    edge[k].cost=-co;               //故這裡去反費用（因為是反向邊）
    edge[k].next=edgeHead[v];
    edge[k].re=k - 1;
    edgeHead[v]=k ++;
}

bool spfa(){                //尋找最長增廣路時如果是正向邊則+相應的費用，反向邊-相應的費用
    int i, head = 0, tail = 1;    //  長注釋的地方就是從最小費用改到最大費用時需要變動的地方
    for(i = 0; i <= n; i ++){
        dis[i] = inf;
        vis[i] = false;
    }
    dis[0] = 0;
    que[0] = 0;
    vis[0] = true;
    while(head != tail){
        int u = que[head];
        for(i = edgeHead[u]; i != 0; i = edge[i].next){
            int v = edge[i].v;
            if(edge[i].cap && dis[v] >dis[u] + edge[i].cost){
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;                        // 這個pre數組記錄的是從邊号為i的那條邊去往v
                if(!vis[v]){
                    vis[v] = true;
                    que[tail ++] = v;
                    if(tail == 490) tail = 0;             // 這裡用到了循環隊列，節省空間
                }
            }
        }
        vis[u] = false;
        head++;
        if(head ==490) head = 0;
    }
    if(dis[n] ==inf) return false;///
    return true;
}

void end(){
    int u, p,mi;
	mi=inf;
	for(u = n; u != 0; u = edge[edge[p].re].v){
        p = pre[u];
        if(edge[p].cap<mi)
            mi=edge[p].cap;
    }
    for(u = n; u != 0; u = edge[edge[p].re].v){
        p = pre[u];
        edge[p].cap -= mi;
        edge[edge[p].re].cap += mi;
        ans += edge[p].cost*mi;
    }
}
int main(){
	int i,j,T,t,v,lim,a,b,w;
	int cnt;
	scanf("%d",&T);
	for(t=1;t<=T;t++){
	    k=1;
	    cnt=0;
		memset(edgeHead,0,sizeof(edgeHead));
		scanf("%d %d",&v,&lim);
		for(i=1;i<=v;i++){
			scanf("%d %d %d",&a,&b,&w);
			li[cnt++]=a;
			li[cnt++]=b;

			line[i].a=a;
			line[i].b=b;
			line[i].w=w;
		}
		sort(li,li+cnt);
		n=unique(li,li+cnt)-li;
		for(i=1;i<=n;i++)
            addEdge(i-1,i,lim,0);
		for(i=1;i<=v;i++){
		    int x=lower_bound(li,li+n,line[i].a)-li+1;
		    int y=lower_bound(li,li+n,line[i].b)-li+1;
			addEdge(x,y,1,-line[i].w);
		}
	    ans=0;
		while(spfa())end();
		printf("%d\n",-ans);
	}
    return 0;
}