POJ 3680: Intervals【最小费用最大流】

题目大意：你有N个开区间，每个区间有个重量wi，你要选择一些区间，使得满足：每个点被不超过K个区间覆盖的前提下，重量最大

思路：感觉是很好想的费用流，把每个区间首尾相连，费用为该区间的重量的相反数（由于要最大，所以是求最大费用最大流），容量为1，至于不超过K的限制，只要从源点到第一个点的流量为K就行，剩下每个相邻的点相连，费用为0，流量只要大于的等于K就可以（我取的正无穷）

//poj3680

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <algorithm>

#include <queue>

#define maxn 120090

#define esp 0.00001

#define inf 0x3f3f3f3f

using namespace std;

int head[maxn],point[maxn],flow[maxn],next[maxn];

int now=0,value[maxn],k,xx,yy,vv,x[maxn],y[maxn];

int v[maxn],h=0,inte[maxn],id[maxn],root[maxn],n;

int dist[maxn],pre[maxn],j;

void add(int x,int y,int f,int v)

{

next[++now]=head[x];

head[x]=now;

point[now]=y;

flow[now]=f;

value[now]=v;

root[now]=x;

next[++now]=head[y];

head[y]=now;

point[now]=x;

flow[now]=0;

value[now]=-v;

root[now]=y;

}

int spfa(int s,int t)

{

for(int i=1;i<=j;i++)dist[i]=200000;

dist[t]=200000;

dist[s]=0;

int visit[maxn]={0};

visit[s]=1;

queue<int>q;

q.push(s);

while(!q.empty())

{

int u=q.front();

q.pop();

visit[u]=0;

for(int i=head[u];i;i=next[i])

{

int k=point[i];

if(dist[u]+value[i]<dist[k] && flow[i])

{

dist[k]=dist[u]+value[i];

pre[k]=i;

if(!visit[k])

{

visit[k]=1;

q.push(k);

}

if(dist[t]==200000)return 0;else return 1;

}

int main()

{

int tt;

scanf("%d",&tt);

while(tt--)

{

int ans=0;

now=0;h=0;

memset(head,0,sizeof(head));

memset(pre,0,sizeof(pre));

scanf("%d%d",&n,&k);

for(int i=1;i<=n;i++)

{

scanf("%d%d%d",&xx,&yy,&vv);

x[i]=xx;y[i]=yy;v[i]=vv;

inte[++h]=xx;inte[++h]=yy;

}

sort(inte+1,inte+1+h);

j=1;

id[inte[1]]=1;

for(int i=2;i<=h;i++)

{

if(inte[i]!=inte[j])

{

inte[++j]=inte[i];

id[inte[j]]=j;

}

for(int i=1;i<=j;i++)

add(i,i+1,inf,0);

for(int i=1;i<=n;i++)

{

add(id[x[i]],id[y[i]],1,-v[i]);

}

int s=maxn-10,t=maxn-100;

add(s,1,k,0);

add(j,t,k,0);

while(spfa(s,t))

{

int e=pre[t],minx=flow[e];

while(e)

{

minx=min(minx,flow[e]);

e=pre[root[e]];

}

e=pre[t];

while(e)

{

flow[e]-=minx;

flow[((e-1)^1)+1]+=minx;

e=pre[root[e]];

}

ans+=dist[t]*minx;

}

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

}

return 0;

}

巴特西

POJ 3680: Intervals【最小费用最大流】

最新文章

热门文章