Intervals
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 7161 Accepted: 2982
Description
You are given N weighted open intervals. The ith interval covers (ai, bi) and weighs wi. Your task is to pick some of the intervals to maximize the total weights under the limit that no point in the real axis is covered more than k times.
Input
The first line of input is the number of test case.
The first line of each test case contains two integers, N and K (1 ≤ K ≤ N ≤ 200).
The next N line each contain three integers ai, bi, wi(1 ≤ ai < bi ≤ 100,000, 1 ≤ wi ≤ 100,000) describing the intervals.
There is a blank line before each test case.
Output
For each test case output the maximum total weights in a separate line.
Sample Input
4 3 1 1 2 2 2 3 4 3 4 8 3 1 1 3 2 2 3 4 3 4 8 3 1 1 100000 100000 1 2 3 100 200 300 3 2 1 100000 100000 1 150 301 100 200 300Sample Output
14 12 100000 100301Source
, windy7926778
费用流，构图方法很巧妙。
我一开始的想法是区间放左边，点放右边，跑费用流。后来发现显然是错的，因为在最大流时源点流入区间的边不一定满流，也就是一个区间内的点没有全部覆盖，这显然是错误的。
下面是正确地做法：要保证每个点最多覆盖k次，可以把所有点串联起来，每个点向后一个点连一条容量k、费用0的边。(是不是很机智啊！！)然后对于区间[a,b]，从a到b连一条容量1、费用w的边就可以了。最后从源点到1点、从n点到汇点，分别连一条容量k、费用0的点。
至于这个方法的正确性如何证明呢？？我可以说只可意会不可言传吗=_=……大家自己脑补吧……额
如此看来，构图真是一种艺术啊！
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define LL long long
#define pa pair<int,int>
#define maxn 1000
#define maxm 1000
#define inf 1000000000
using namespace std;
int tt,n,k,s,t,cnt,ans,tot;
int head[maxn],dis[maxn],p[maxn],a[maxn],b[maxn],w[maxn],f[maxn];
bool inq[maxn];
map<int,int> mp;
struct edge_type
{
int from,to,next,v,c;
}e[maxm];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add_edge(int x,int y,int v,int c)
{
e[++cnt]=(edge_type){x,y,head[x],v,c};head[x]=cnt;
e[++cnt]=(edge_type){y,x,head[y],0,-c};head[y]=cnt;
}
inline bool spfa()
{
queue<int>q;
memset(inq,false,sizeof(inq));
F(i,1,t) dis[i]=inf;
dis[s]=0;q.push(s);inq[s]=true;
while (!q.empty())
{
int x=q.front();q.pop();inq[x]=false;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (e[i].v&&dis[y]>dis[x]+e[i].c)
{
dis[y]=dis[x]+e[i].c;
p[y]=i;
if (!inq[y]){q.push(y);inq[y]=true;}
}
}
}
return dis[t]!=inf;
}
inline void mcf()
{
ans=0;
while (spfa())
{
int tmp=inf;
for(int i=p[t];i;i=p[e[i].from]) tmp=min(tmp,e[i].v);
ans+=tmp*dis[t];
for(int i=p[t];i;i=p[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;}
}
}
int main()
{
tt=read();
while (tt--)
{
memset(head,0,sizeof(head));
memset(p,0,sizeof(p));
memset(f,0,sizeof(f));
cnt=1;tot=0;
n=read();k=read();
F(i,1,n)
{
a[i]=read();b[i]=read();w[i]=read();
f[2*i-1]=a[i];f[2*i]=b[i];
}
sort(f+1,f+2*n+1);
F(i,1,2*n) if (i==1||f[i]!=f[i-1]) mp[f[i]]=++tot;
s=tot+1;t=tot+2;
F(i,1,tot-1) add_edge(i,i+1,k,0);
add_edge(s,1,k,0);add_edge(tot,t,k,0);
F(i,1,n) add_edge(mp[a[i]],mp[b[i]],1,-w[i]);
mcf();
printf("%d\n",-ans);
}
}
顶 0 踩 0
我的同类文章
猜你在找
查看评论
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
个人资料
AaronGZK
积分：1501
联系方式
QQ：1045980567
Email：guozhongkang@hotmail.com
友情链接
Elemmir
fqqq
Gvolv
Hist!
Regina8023
Ryan
Vkrms
wjyi
ZYF-ZYF
文章搜索
博客专栏
文章：41篇
阅读：15167
相关文章
精彩导读
热门资讯
关注我们
