锐客网

  1. 首页 > it技术 > >

POJ|POJ 3680 最小费用最大流

这题来源：《算法竞赛经典入门-训练指南》中的367页：区间k覆盖问题。
思路：这题建图比较机智，我刚开始想到能建的图也就是离散化后两个端点连边，流量为1，费用为负的权值（因为求的是最大费用最大流），然后再加上源点和汇点，也就如此而已；但是这样建图样例第二和第四个不正确，因为中间没有联系的没连边，然后k就没用了。
原来最重要的连边是i和i+1之间的连边，流量为k，费用为0；为什么要连这些边呢，刚开始我也没想明白，后面才知道，因为有的端点之间你要让它们产生联系并且受制与k次，那么就得把这些点都连边，这样就有联系了嘛！

#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff typedef long long ll; typedef unsigned long long ull; using namespace std; #define maxn 20005 struct { int v,w,c,next,re; //re记录逆边的下标,c是费用,w是流量 } e[maxn]; int n,cnt; int head[maxn],que[maxn*8],pre[maxn],dis[maxn]; bool vis[maxn]; void add(int u, int v, int w, int c) { e[cnt].v=v,e[cnt].w=w,e[cnt].c=c; e[cnt].next=head[u]; e[cnt].re=cnt+1,head[u]=cnt++; e[cnt].v=u,e[cnt].w=0,e[cnt].c=-c; e[cnt].next=head[v]; e[cnt].re=cnt-1,head[v]=cnt++; } bool spfa() { int i, l = 0, r = 1; for(i = 0; i <= n; i ++) dis[i] = INF,vis[i] = false; dis[0]=0,que[0]=0,vis[0]=true; while(ldis[u]+e[i].c) { dis[v] = dis[u] + e[i].c; pre[v] = i; if(!vis[v]) { vis[v] = true; que[r++] = v; } } } vis[u] = false; } return dis[n]!=INF; } int change() { int i,p,sum=INF,ans=0; for(i=n; i!=0; i=e[e[p].re].v) {//e[e[p].re].v为前向结点,不理解看add和spfa p=pre[i]; //p为前向结点编号 sum=min(sum,e[p].w); } for(i=n; i!=0; i=e[e[p].re].v) { p=pre[i]; e[p].w-=sum; e[e[p].re].w+=sum; ans+=sum*e[p].c; //c记录的为单位流量费用，必须得乘以流量。 } return ans; } int EK() { int sum=0; while(spfa()) sum+=change(); return sum; } void init() { mem(head,-1),mem(pre,0),cnt=0; } struct abc { int u,v,w; }aa[405]; int main() { //freopen("1.txt","r",stdin); int t; scanf("%d",&t); while(t--) { init(); int N,K,i,j,x,y,tmp=0,a[402]; mapMap; scanf("%d%d",&N,&K); for(i=0; i



【POJ|POJ 3680 最小费用最大流】

    推荐阅读


    上一篇：Java使用HttpsURLConnection进行Get和Post请求（绕过证书验证）

    下一篇：PHP中,将变量值作为变量名