poj 3680(最小费用最大流)

思路：因为N<=200,而区间范围为【1，100000】，因此需要离散化，去重，然后就是建图了相连两点连边，容量为k,费用为0，然后就是对区间端点进行连边，容量为1，费用为权值，最后就是跑费用流了。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 #define MAXN 444
  8 #define MAXM 444444
  9 #define inf 1<<30
 10 
 11 struct Edge{
 12     int v,cap,cost,next;
 13 }edge[MAXM];
 14 
 15 int vs,vt,NE,n,m;
 16 int head[MAXN];
 17 
 18 void Insert(int u,int v,int cap,int cost)
 19 {
 20     edge[NE].v=v;
 21     edge[NE].cap=cap;
 22     edge[NE].cost=cost;
 23     edge[NE].next=head[u];
 24     head[u]=NE++;
 25 
 26     edge[NE].v=u;
 27     edge[NE].cap=0;
 28     edge[NE].cost=-cost;
 29     edge[NE].next=head[v];
 30     head[v]=NE++;
 31 }
 32 
 33 int pre[MAXN],cur[MAXN];
 34 int dist[MAXN];
 35 bool mark[MAXN];
 36 bool spfa(int vs,int vt)
 37 {
 38     memset(mark,false,sizeof(mark));
 39     fill(dist,dist+vt+1,-inf);
 40     dist[vs]=0;
 41     queue<int>que;
 42     que.push(vs);
 43     while(!que.empty()){
 44         int u=que.front();
 45         que.pop();
 46         mark[u]=false;
 47         for(int i=head[u];i!=-1;i=edge[i].next){
 48             int v=edge[i].v;
 49             if(edge[i].cap>0&&dist[u]+edge[i].cost>dist[v]){
 50                 dist[v]=dist[u]+edge[i].cost;
 51                 pre[v]=u;
 52                 cur[v]=i;
 53                 if(!mark[v]){
 54                     mark[v]=true;
 55                     que.push(v);
 56                 }
 57             }
 58         }
 59     }
 60     return dist[vt]!=-inf;
 61 }
 62 
 63 int MinCostFlow(int vs,int vt)
 64 {
 65     int flow=0,cost=0;
 66     while(spfa(vs,vt)){
 67         int aug=inf;
 68         for(int u=vt;u!=vs;u=pre[u]){
 69             aug=min(aug,edge[cur[u]].cap);
 70         }
 71         flow+=aug,cost+=dist[vt]*aug;
 72         for(int u=vt;u!=vs;u=pre[u]){
 73             edge[cur[u]].cap-=aug;
 74             edge[cur[u]^1].cap+=aug;
 75         }
 76     }
 77     return cost;
 78 }
 79 
 80 struct Line{
 81     int u,v,w;
 82 }line[MAXN];
 83 
 84 int num[MAXN];
 85 
 86 int main()
 87 {
 88  //   freopen("1.txt","r",stdin);
 89     int _case,cnt=0;
 90     scanf("%d",&_case);
 91     while(_case--){
 92         scanf("%d%d",&n,&m);
 93         cnt=NE=0;
 94         memset(head,-1,sizeof(head));
 95         for(int i=1;i<=n;i++){
 96             scanf("%d%d%d",&line[i].u,&line[i].v,&line[i].w);
 97             num[cnt++]=line[i].u;
 98             num[cnt++]=line[i].v;
 99         }
100         sort(num,num+cnt);
101         cnt=unique(num,num+cnt)-num;
102         for(int i=1;i<=cnt;i++){
103             Insert(i-1,i,m,0);
104         }
105         for(int i=1;i<=n;i++){
106             int a=lower_bound(num,num+cnt,line[i].u)-num+1;
107             int b=lower_bound(num,num+cnt,line[i].v)-num+1;
108             Insert(a,b,1,line[i].w);
109         }
110         printf("%d
",MinCostFlow(0,cnt));
111     }
112     return 0;
113 }
View Code