POJ3680_Intervals

给你若干个区间,每个区间有一个权值,你可以选出某些区间,使得在保证没有任何一段的覆盖次数超过k的前提下,总的权值最大。

这个建模真的十分神奇,赞一个。

对于给出的每一个区间,离散化,最终我们可以知道所有区间的端点的个数不会超过2n,然后我们加边,(i,i+1,k,0),对于每个区间我们加边(li,ri,1,-wi)。

这样我们跑出最小费用,就是答案了,仔细理解一下就知道了,这就是题目的等价模型,保证了流量的限制。

召唤代码君:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 422
#define maxm 84444
using namespace std; int to[maxm],cap[maxm],cost[maxm],next[maxm],first[maxn],edge;
int d[maxn],num[maxn],from[maxn],tag[maxn],TAG=;
int Q[maxm],bot,top;
int a[maxm],u[maxn],v[maxn],w[maxn];
int n,m,N,K,T,s,t,ans; void _init()
{
s=,t=n+,ans=,edge=-;
for (int i=s; i<=t; i++) first[i]=-;
} void addedge(int U,int V,int W,int C)
{
edge++;
to[edge]=V,cap[edge]=W,cost[edge]=C,next[edge]=first[U],first[U]=edge;
edge++;
to[edge]=U,cap[edge]=,cost[edge]=-C,next[edge]=first[V],first[V]=edge;
} bool bfs()
{
Q[bot=top=]=s,tag[s]=++TAG,d[s]=,num[s]=K,from[s]=-;
while (bot<=top){
int cur=Q[bot++];
for (int i=first[cur]; i!=-; i=next[i])
if (cap[i]> && (tag[to[i]]!=TAG || d[cur]+cost[i]<d[to[i]])){
tag[to[i]]=TAG;
num[to[i]]=min(num[cur],cap[i]);
d[to[i]]=d[cur]+cost[i];
from[to[i]]=i;
Q[++top]=to[i];
}
}
if (tag[t]!=TAG || d[t]>=) return false;
ans+=num[t]*d[t];
for (int i=t; from[i]!=-; i=to[from[i]^])
cap[from[i]]-=num[t],cap[from[i]^]+=num[t];
return true;
} int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&N,&K);
for (int i=; i<N; i++){
scanf("%d%d%d",&u[i],&v[i],&w[i]);
a[i]=u[i],a[i+N]=v[i];
}
sort(a,a+N+N);
n=unique(a,a+N+N)-a;
for (int i=; i<N; i++){
u[i]=lower_bound(a,a+n,u[i])-a+;
v[i]=lower_bound(a,a+n,v[i])-a+;
}
_init();
for (int i=; i<=n; i++) addedge(i,i+,K,);
for (int i=; i<N; i++) addedge(u[i],v[i],,-w[i]);
while (bfs()) ;
printf("%d\n",-ans);
}
return ;
}
上一篇:关于 unsigned int 比较大小


下一篇:Python基本知识 os.path.join与split() 函数