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
",-mincost());
}
return 0;
}
사실 이 문제도 i+1에서 i로 용량이 1이고 권한이 w[i]인 사이드에서 구한 최소 비용 흐름에서 모든 구간 권한과 마이너스를 빼면 됩니다. 사실상 최소 비용 흐름에 대응하는 구간 이외의 구간입니다. 도면을 작성하여 각 점이 K구간을 초과하지 않도록 하기 때문에 제목과 일치하지 않을 염려가 없습니다.
하루 종일교묘한 구도~~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.