POJ 3680_Intervals

題意：

給定區間和該區間對應的權值，挑選一些區間，求使得每個數都不被K個區間覆蓋的最大權值和。

分析：

如果K=1，即為區間圖的最大權獨立集問題。可以對區間所有端點排序后利用動態規劃的方法，設dp[i]為只考慮區間右端點小于等于xi的區間所得到的最大總權重。

dp[i] = max(dp[i - 1], max{dp[j] + w[k])|a[k] = x[j]且b[k] = x[i]}

K>1，既然求權重最大值，利用最小費用流，很容易想到從a[i]到b[i]連一條容量為1，費用為?w[i]的邊，但是如何限制每個數不被超過K個區間覆蓋呢？從i到i+1連一條容量為K，費用為0的邊，這樣便限制了流經每個端點的流量不超過K，也就滿足每個數不被超過K個區間覆蓋啦~注意區間端點的離散化~~

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int maxn = 505, maxm = 1000;
const int INF = 0x3f3f3f3f;
int s, t, tot;
int dist[maxm], prevv[maxm], preve[maxm], head[maxm];
int a[maxn], b[maxn], w[maxn], tt[maxm];
bool in[maxn];
struct Edge{ int from, to, next, cap, cost;}edge[maxm * 3];
void add_edge(int from, int to, int cap, int cost)
{edge[tot].to = to;edge[tot].from = from;edge[tot].cap = cap;edge[tot].cost = cost;edge[tot].next = head[from];head[from] = tot++;edge[tot].to = from;edge[tot].from = to;edge[tot].cap = 0;edge[tot].cost = -cost;edge[tot].next = head[to];head[to] = tot++;
}
int mincost()
{int flow=0, cost=0;for(;;){memset(dist, 0x3f, sizeof(dist));memset(in, false, sizeof(in));queue<int>q;q.push(s);in[s] = true;dist[s]=0;while(!q.empty()){int u = q.front();q.pop();in[u] = false;for(int i = head[u]; i != -1; i = edge[i].next){Edge e = edge[i];if(e.cap>0 && dist[e.to] > dist[u] + e.cost){dist[e.to] = dist[u] + e.cost;prevv[e.to] = u, preve[e.to] = i;if(!in[e.to]){in[e.to] = true;q.push(e.to);}}}}if(dist[t] == INF)  return cost;int d = INF;for(int i = t; i != s; i = prevv[i])d = min(d, edge[preve[i]].cap);flow += d;cost += dist[t] * d;for(int i = t; i != s; i = prevv[i]){edge[preve[i]].cap -= d;edge[preve[i]^1].cap += d;}}
}
int main()
{int c;scanf("%d",&c);while(c--){int N, K;memset(head,-1,sizeof(head));tot = 0;int n = 0;scanf("%d%d",&N, &K);for(int i = 0; i < N; i++){scanf("%d%d%d", &a[i], &b[i], &w[i]);tt[n++] = a[i];tt[n++] = b[i];}sort(tt, tt + n);int nn = unique(tt, tt +n) - tt;int na, nb;for(int i = 0; i < N; i++){na = lower_bound(tt, tt + nn, a[i]) - tt;nb = lower_bound(tt, tt + nn, b[i]) - tt;add_edge(na + 1, nb + 1, 1, -w[i]);}s = 0, t = nn + 1;add_edge(s, 1, K, 0);for(int i = 1; i <= nn; i++)add_edge(i, i + 1, K, 0);printf("%d\n",-mincost());}return 0;
}

---

其實這題也可以是從i+1向i連一條容量為1，權值為w[i]的邊，用求出的最小費用流減去所有區間權值和，再取負數就好啦~實際上是取最小費用流對應的區間之外的區間，因為建圖保證每個點都不被超過K個區間覆蓋，所以不用擔心與題目不符啦~~

---

tle了一整天。。。。
很巧妙的構圖~~~