[POJ 3680]费用流**

【题目大意】 数轴上有N个区间，每个区间有一个权值C，你可以选择任意多的区间，但是数轴上某一段不能被覆盖超过K次，求最大能获得的权值。

【算法分析】这个连边感觉比较巧，不过挺容易理解。
就是先离散化，然后i向i+1连边，容量为limit，费用为0
然后再对于每个区间连边a[i]->b[i]，容量为1，费用为w[i]
新增源汇，连边[S,1]，容量为limit，费用为0
连边[n,T]，容量为limit，费用为0
实际到达每一个点的话就相当于选择是否分配流到以这个点位起点的区间边上，然后再向后流去。
做一次最大费用最大流即可。

【其它】1A
6401617 edward2 3680 Accepted 644K 407MS G++ 2404B 2010-02-02 18:50:17
【CODE】
#include #include #include #include using namespace std;
#define N 1000
struct gtp{int x,y,next,w,c,op;}g[10000];
int n,e,m,limit,cost;
int a[N],b[N],w[N],zb[N];
int ls[N],fa[N],d[N],v[N],list[N];

void init(){
scanf("%d%d",&m,&limit);
for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&w[i]);
}

void lisan(){
int tail=0;
for (int i=1;i<=m;i++){
zb[++tail]=a[i];
zb[++tail]=b[i];
}
sort(&zb[1],&zb[tail+1]);
n=0;
for (int i=1;i<=tail;i++)
if (n==0 || zb[n]!=zb[i]) zb[++n]=zb[i];
}

void add(int x,int y,int c,int w){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w;
g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

int find(int x){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (x>zb[mid]) l=mid+1;
else r=mid;
}
return l;
}

void build(){
e=0; memset(ls,0,sizeof(ls));
for (int i=0;i<=n;i++) add(i,i+1,limit,0);
for (int i=1;i<=m;i++)
add(find(a[i]),find(b[i]),1,w[i]);
}

bool spfa(){
for (int i=0;i<=n+1;i++){
d[i]=-1;
v[i]=0;
}
d[0]=0; v[0]=1; list[0]=0;
int head=-1,tail=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t;t=g[t].next)
if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
d[g[t].y]=d[g[t].x]+g[t].w;
fa[g[t].y]=t;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
if (d[n+1]==-1) return false;
return true;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=n+1;i!=0;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=n+1;i!=0;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
cost+=nf*d[n+1];
}

void mincost_maxflow(){
cost=0;
while (spfa()) change();
}

int main(){
int tc;
scanf("%d",&tc);
for (int i=0;i init();
lisan();
build();
mincost_maxflow();
printf("%dn",cost);
}
}