poj 3680 Intervals(费用流)

巧妙的构图。

题目：给定N个区间（ai，bi）权值wi，求最大权和且每个点最多覆盖K次。

构图：将区间端点离散化，将第i个点连第i+1个点花费为0，容量为INF，即addedge(i,i+1,0,INF)（可用来跳过一些区间）;

　　　再处理N个区间（ai，bi），addedge(ai,bi,-wi,1);

　　　最后源点连第一个点，addedge(src,1,0,k);最后一个点连汇点,addedge(n,sink,0,k)。

原理：构完图之后做最小费用最大流，其实就是找不大于K条增广路。如果两个区间有交集，则不能一次流过，要分成两条增广路流过；反之，则可一次流过。

 /*

  *Author:       Zhaofa Fang

  *Created time: 2013-07-19-10.41

  *Language:     C++

  */

 #include <cstdio>

 #include <cstdlib>

 #include <sstream>

 #include <iostream>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 #include <string>

 #include <utility>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> PII;

 #define DEBUG(x) cout<< #x << ':' << x << endl

 #define FOR(i,s,t) for(int i = (s);i <= (t);i++)

 #define FORD(i,s,t) for(int i = (s);i >= (t);i--)

 #define REP(i,n) for(int i=0;i<(n);i++)

 #define REPD(i,n) for(int i=(n-1);i>=0;i--)

 #define PII pair<int,int>

 #define PB push_back

 #define MP make_pair

 #define ft first

 #define sd second

 #define lowbit(x) (x&(-x))

 #define INF (1<<30)

 #define eps (1e-8)

 const int maxm = ;

 const int maxn = ;

 int ans,anscost;

 struct Edge {

     int u,v,cost,cap,flow,next;

 }et[maxm];

 int S,T;

 int eh[maxn],tot,low[maxn],p[maxn],dist[maxn];

 bool vist[maxn];

 bool spfa(){

     queue<int>que;

     memset(vist,,sizeof(vist));

     memset(p,-,sizeof(p));

     fill(dist,dist+maxn,INF);

     vist[S] = ,low[S] = INF,dist[S] = ;

     que.push(S);

     while(!que.empty()){

         int u = que.front();

         que.pop();

         vist[u] = false;

         for(int i=eh[u];i!=-;i=et[i].next){

             int v = et[i].v,cost = et[i].cost,cap=et[i].cap,flow=et[i].flow;

             if(flow < cap && dist[u] + cost < dist[v]){

                 dist[v] = dist[u] + cost;

                 p[v] = i;

                 low[v] = min(low[u],cap-flow);

                 if(!vist[v]){

                     vist[v] = ;

                     que.push(v);

                 }

             }

         }

     }

     return dist[T]!=INF;

 }

 void costflow(){

     ans = ,anscost = ;

     int num=;

     while(spfa()){

         int x = p[T];

         ans += low[T];

         anscost += low[T]*dist[T];

         while(x!=-){

             et[x].flow += low[T];

             et[x^].flow -= low[T];

             et[x^].cost = -et[x].cost;

             x = p[et[x].u];

         }

     }

 }

 void add(int u,int v,int cost,int cap,int flow){

     Edge e = {u,v,cost,cap,flow,eh[u]};

     et[tot] = e;

     eh[u] = tot ++;

 }

 void addedge(int u,int v,int cost,int cap){

     add(u,v,cost,cap,);add(v,u,-cost,,);

 }

 void init(){

     tot = ;

     memset(eh,-,sizeof(eh));

 }

 int X[maxn];

 int a[maxn],b[maxn],w[maxn];

 int find(int key,int n){

     int r = lower_bound(X,X+n,key)-X;

     return r+;

 }

 int main(){

     //freopen("in","r",stdin);

     //freopen("out","w",stdout);

     int Ca;

     scanf("%d",&Ca);

     while(Ca--){

         int N,K;

         scanf("%d%d",&N,&K);

         int cnt = ;

         init();

         REP(i,N){

             scanf("%d%d%d",&a[i],&b[i],&w[i]);

             X[cnt++]=a[i];X[cnt++]=b[i];

             w[i] = -w[i];

         }

         sort(X,X+cnt);

         int n = ;

         FOR(i,,cnt-){

             if(X[i]!=X[i-])X[n++]=X[i];

         }

         REP(i,n-){

             addedge(i+,i+,,INF);

         }

         REP(i,N){

             int l = find(a[i],n);

             int r = find(b[i],n);

             addedge(l,r,w[i],);

         }

         addedge(,,,K);

         addedge(n,n+,,K);

         S = ;T = n+;costflow();

         printf("%d\n",-anscost);

     }

     return ;

 }

1300+MS

秒客网

poj 3680 Intervals(费用流)

相关文章