POJ 1459Power Network(网络流最大流 ISAP算法)

时间：2023-05-28 08:06:13 其他范文收藏本文下载本文

下面是小编为大家带来的POJ 1459Power Network(网络流最大流 ISAP算法)，本文共5篇，希望大家能够喜欢!

篇1：POJ 1459Power Network(网络流最大流 ISAP算法)

Power NetworkTime Limit:MSMemory Limit:32768KTotal Submissions:23724Accepted:12401

Description

A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node u may be supplied with an amount s(u) >= 0 of power, may produce an amount 0<= p(u)<= pmax(u) of power, may consume an amount 0<= c(u)<= min(s(u),cmax(u)) of power, and may deliver an amount d(u)=s(u)+p(u)-c(u) of power. The following restrictions apply: c(u)=0 for any power station, p(u)=0 for any consumer, and p(u)=c(u)=0 for any dispatcher. There is at most one power transport line (u,v) from a node u to a node v in the net; it transports an amount 0<= l(u,v)<= lmax(u,v) of power delivered by u to v. Let Con=Σuc(u) be the power consumed in the net. The problem is to compute the maximum value of Con.

An example is in figure 1. The label x/y of power station u shows that p(u)=x and pmax<?www.2cto.com/kf/ware/vc/“ target=”_blank“ class=”keylink“>vc3ViPih1KT15LiBUaGUgbGFiZWwgeC95IG9mIGNvbnN1bWVyIHUgc2hvd3MgdGhhdCBjKHUpPXggYW5kIGM8c3ViPm1heDwvc3ViPih1KT15LiBUaGUgbGFiZWwgeC95IG9mIHBvd2VyIHRyYW5zcG9ydCBsaW5lICh1LHYpIHNob3dzIHRoYXQgbCh1LHYpPXggYW5kIGw8c3ViPm1heDwvc3ViPih1LHYpPXkuCiBUaGUgcG93ZXIgY29uc3VtZWQgaXMgQ29uPTYuIE5vdGljZSB0aGF0IHRoZXJlIGFyZSBvdGhlciBwb3NzaWJsZSBzdGF0ZXMgb2YgdGhlIG5ldHdvcmsgYnV0IHRoZSB2YWx1ZSBvZiBDb24gY2Fubm90IGV4Y2VlZCA2LiA8YnI+Cgo8cCBjbGFzcz0=”pst“>Input

There are several data sets in the input. Each data set encodes a power network. It starts with four integers: 0<= n<= 100 (nodes), 0<= np<= n (power stations), 0<= nc<= n (consumers), and 0<= m<= n^2 (power transport lines). Follow m data triplets (u,v)z, where u and v are node identifiers (starting from 0) and 0<= z<= 1000 is the value of lmax(u,v). Follow np doublets (u)z, where u is the identifier of a power station and 0<= z<= 10000 is the value of pmax(u). The data set ends with nc doublets (u)z, where u is the identifier of a consumer and 0<= z<= 10000 is the value of cmax(u). All input numbers are integers. Except the (u,v)z triplets and the (u)z doublets, which do not contain white spaces, white spaces can occur freely in input. Input data terminate with an end of file and are correct.

Output

For each data set from the input, the program prints on the standard output the maximum amount of power that can be consumed in the corresponding network. Each result has an integral value and is printed from the beginning of a separate line.

Sample Input

2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)207 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7 (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5 (0)5 (1)2 (3)2 (4)1 (5)4

Sample Output

156

Hint

The sample input contains two data sets. The first data set encodes a network with 2 nodes, power station 0 with pmax(0)=15 and consumer 1 with cmax(1)=20, and 2 power transport lines with lmax(0,1)=20 and lmax(1,0)=10. The maximum value of Con is 15. The second data set encodes the network from figure 1.

题意：有n个结点，np个发电站，nc个消费者，m个电力运输线，接下去是n条边的信息(u,v)cost，cost表示边(u,v)的最大流量；a个发电站的信息(u)cost，cost表示发电站u能提供的最大流量；b个用户的信息(v)cost，cost表示每个用户v能接受的最大流量。

思路：在图中添加1个源点S和汇点T，将S和每个发电站相连，边的权值是发电站能提供的最大流量；将每个用户和T相连，边的权值是每个用户能接受的最大流量，

从而转化成了一般的最大网络流问题，然后求解。（自己语言总结不好，觉得这个能看懂，就贴一下）

#include#include#include#include#include #include#include#include#includeusing namespace std;const int inf=0x3f3f3f3f;int head[10010],num[10010],d[10010],cur[10010],q[10010],pre[10010];int n,m,s,t,cnt,nv;int maxint=inf;struct node { int v,cap; int next;} edge[100010];void add(int u,int v,int cap){ edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].next=head[v]; head[v]=cnt++;}void bfs{ int i,j; memset(num,0,sizeof(num)); memset(d,-1,sizeof(d)); int f1=0,f2=0; q[f1++]=t; d[t]=0; num[0]=1; while(f1>=f2) { int u=q[f2++]; for(i=head[u]; i!=-1; i=edge[i].next) {int v=edge[i].v;if(d[v]!=-1) continue;d[v]=d[u]+1;num[d[v]]++;q[f1++]=v; } }}void isap(){ memcpy(cur,head,sizeof(cur)); bfs(); int flow=0,u=pre[s]=s,i; while(d[s]edge[cur[i]].cap) { f=edge[cur[i]].cap; pos=i; }}for(i=s; i!=t; i=edge[cur[i]].v) { edge[cur[i]].cap-=f; edge[cur[i]^1].cap+=f;}flow+=f;u=pos; } for(i=cur[u]; i!=-1; i=edge[i].next) {if(d[edge[i].v]+1==d[u]&&edge[i].cap) break; } if(i!=-1) {cur[u]=i;pre[edge[i].v]=u;u=edge[i].v; } else {if(--num[d[u]]==0) break;int mind=nv;for(i=head[u]; i!=-1; i=edge[i].next) { if(mind>d[edge[i].v]&&edge[i].cap) { mind=d[edge[i].v]; cur[u]=i; }}d[u]=mind+1;num[d[u]]++;u=pre[u]; } } printf(”%d\n“,flow);}int main(){ int np, nc,a, b, c; char ch; while(scanf(”%d%d%d%d“,&n,&np,&nc,&m)!=EOF) { memset(head,-1,sizeof(head)); cnt=0; s=0; t=n+1; nv=n+2; while(m--) {while(getchar()!='(');scanf(”%d,%d)%d“,&a,&b,&c);add(a+1,b+1,c); } while(np--) {while(getchar()!='(');scanf(”%d)%d“,&a,&c);add(0,a+1,c); } while(nc--) {while(getchar()!='(');scanf(”%d)%d“,&a,&c);add(a+1,t,c); } isap(); } return 0;}

篇2：poj 1698Alices Chance 最大流题

//建立一个超级源点和一个超级汇点

//从超级源点到每一个film的权值为需要在这个film工作的天数D

//然后从film到每个星期的第j天为一条权值为1的边

//从每个星期的第j天到超级汇点的权值为1

//这样就可以只需要验证从超级源点到超级汇点的最大流是否和所有film的天数之和是否相等

#include

using namespace std;

#define maxn 1010

#define inf 0x7fffffff

struct node

{

int to;

int cap;

int next;

}edge[maxn*1000];

int nedge=0;

int head[maxn];

queueque;

int dis[maxn];

int st=0;

int en=1001;

void add(int u,int v,int cap)

{

edge[nedge].to=v;

edge[nedge].cap=cap;

edge[nedge].next=head[u];

head[u]=nedge++;

edge[nedge].to=u;

edge[nedge].cap=0;

edge[nedge].next=head[v];

head[v]=nedge++;

}

int bfs()

{

int i;

memset(dis,-1,sizeof(dis));

while(que.size())

que.pop();

dis[st]=0;

que.push(st);

while(que.size())

{

int u=que.front();

que.pop();

for(i=head[u];i!=-1;i=edge[i].next)

{

int v=edge[i].to;

if(dis[v]<0&&edge[i].cap>0)

{

dis[v]=dis[u]+1;

que.push(v);

}

if(dis[en]>0)

return 1;

return 0;

}

int dfs(int x,int mx)

{

if(x==en)

return mx;

int i;

int ans=0;

int a;

for(i=head[x];i!=-1;i=edge[i].next)

{

int v=edge[i].to;

if(dis[v]==dis[x]+1&&edge[i].cap>0&&(a=dfs(v,min(mx,edge[i].cap))))

{

edge[i].cap-=a;

edge[i^1].cap+=a;

ans+=a;

mx-=a;

if(!mx)

break;

}

if(!ans)

dis[x]=-1;

return ans;

}

int main()

{

// freopen(”in.txt“,”r“,stdin);

int T;

scanf(”%d“, &T);

while(T--)

{

int N,i,j,D,W,vis[maxn],hash[maxn];

int sum = 0;

memset(head,-1,sizeof(dis));

memset(vis,0,sizeof(vis));

nedge=0;

scanf(”%d“ , &N);

for(i = 1; i <= N ;i++)

{

memset(hash,0,sizeof(hash));

for(j = 1 ; j <= 7 ;j++)

{

int t;

scanf(”%d“, &t);

hash[j] = t;

}

scanf(”%d %d“ , &D ,&W);

add(st, i ,D);

sum += D;

while(W--)

{

for(j=1; j<= 7 ;j++)

if(hash[j])

{

add(i, 50+j+W*10 ,1);

if(!vis[50+j+W*10])

{

add(50+j+W*10, en ,1);

vis[50+j+W*10] = 1;

}

int ans = 0;

int res;

while(bfs())

while(res=dfs(0,inf))

ans+=res;

if(ans == sum)

printf(”Yes\n“);

else

printf(”No\n“);

}

return 0;

}

篇3：POJ 3164 Command Network (最小树形图朱刘算法)

最小树形图第一发，

把一个v写成u了。。。。。TLE了一晚上。。。（虽说今晚出去玩了。。）

刚开始看这个算法的时看模板以为又是一个isap。。。。吓得一个哆嗦。但是仔细看了看之后发现还是挺好理解的。写下自己的理解。

朱刘算法其实只有3步，然后不断循环。

1：找到每个点的最小入边。既然是生成树，那么对于每个点来说，只要选一个权值最小的入边就可以了。贪心思想。因为如果不是最小入边，那么它肯定不是最小树形图的一条边，考虑它是没有意义的。

2：找环。找环找的是最小入边构成的新图的环。如果没找到环，那么一棵树就已经形成了，因为树就是没有环的图。再因为边权都是最小的，因此此时最小树形图就已经出来了，停止循环。

3：如果第2步中找到了环，那么这个环就可以缩成一个点。然后构造新图，更新边权。更新边权的方法是：假设某点u在该环上，并设这个环中指向u的边权是in[u]，那么对于每条从u出发的边(u, i, w)，在新图中连接(new, i, w)的边，其中new为新加的人工顶点; 对于每条进入u的边(i, u, w)，在新图中建立边(i, new, w-in[u])的边。之所以是w-in[u]的原因是如果选择了w，那么那个in[u]在树中就是多余的，完全可以删除，所以需要减去，然后再后面的总费用累加中会体现出删掉了这个权值，不理解的画个图就明白了。

至于实现方法还是看代码吧。看不懂的可以留言提问。

代码如下：

#include#include#include#include#include #include#include#include#includeusing namespace std;#define LL __int64#define pi acos(-1.0)//#pragma comment(linker, ”/STACK:1024000000“)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=40000+10;int cnt, n;int color[110], id[110], pre[110];double in[200];struct Point{ double x, y;}fei[200];struct node{ int u, v; double w;}edge[11000];void add(int u, int v, double w){ edge[cnt].u=u; edge[cnt].v=v; edge[cnt++].w=w;}double dist(Point f1, Point f2){ return sqrt((f1.x-f2.x)*(f1.x-f2.x)*1.0+(f1.y-f2.y)*(f1.y-f2.y));}double dmst(int root){ double ans=0; int i, j, u, v, NV=n; while(1){ for(i=1;i<=NV;i++) in[i]=INF;//找最小入边 for(i=0;i

篇4：poj 2289 Jamies Contact Groups 二分+网络流

题意：

让n个点和m个点对应，一个n只能对应一个m,一个m可以对应多个n,对每个n给出他能对应的m点集合，求m对应n多数的最小值，

分析：

网络流+二分。

代码：

//poj 2289//sep9#include#includeusing namespace std; const int maxN=2048; const int maxM=1000000; struct Edge {int v,f,nxt; }e[maxM*2+10]; queueque; int src,sink; int g[maxN+10]; int nume; bool vis[maxN+10]; int dist[maxN+10]; int map[2048][2048]; int n,m;char tmp[4000];void addedge(int u,int v,int c) {e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume;e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume; } void init {memset(g,0,sizeof(g)); nume=1; } void bfs() {while(!que.empty()) que.pop();vis[src]=true;que.push(src); while(!que.empty()){ int u=que.front();que.pop(); for(int i=g[u];i;i=e[i].nxt) if(e[i].f&&!vis[e[i].v]){que.push(e[i].v);dist[e[i].v]=dist[u]+1;vis[e[i].v]=true; }} } int dfs(int u,int delta) {if(u==sink) return delta;int ret=0;for(int i=g[u];delta&&i;i=e[i].nxt) if(e[i].f&&dist[e[i].v]==dist[u]+1){ int dd=dfs(e[i].v,min(e[i].f,delta)); e[i].f-=dd; e[i^1].f+=dd; delta-=dd; ret+=dd; } return ret; } int dinic(int maxx) { init(); src=0,sink=n+m+1; int i,j; for(i=1;i<=n;++i) addedge(src,i,1); for(i=1;i<=n;++i) for(j=1;j<=m;++j) if(map[i][j]==1) addedge(i,n+j,1); for(i=1;i<=m;++i) addedge(n+i,sink,maxx); int ret=0;while(1){ memset(vis,0,sizeof(vis)); memset(dist,0,sizeof(dist)); bfs(); if(!vis[sink]) break; ret+=dfs(src,INT_MAX);} if(ret==n)return 1; return 0;} int main() { while(scanf(”%d%d“,&n,&m)==2){ if(n==0&&m==0) break; int i,j; getchar(); memset(map,0,sizeof(map)); for(int i=1;i<=n;i++) { gets(tmp); int len=strlen(tmp); for(int j=0;j='0'&&tmp[j]<='9') { int v=0; while(tmp[j]>='0'&&tmp[j]<='9'){ v=v*10+tmp[j++]-'0'; } map[i][v+1]=1; }} } int ans,l,r; l=0,r=n+1; while(l

篇5：运输网络转运结点有容量限制的最大流分配算法

运输网络转运结点有容量限制的最大流分配算法

对运输网络转运结点有容量限制的最大流分配一般是用结点一分为二的方法,但在大型、复杂的运输网络中,当有容量限制的结点很多时,这种方法将会使运输网络变得更加庞大,流量分配的`过程变得更加繁琐.通过分析容量限制结点的特点,基于寻找增流链的算法,构造了基于大型、复杂运输网络中结点有容量限制的最大流分配算法.利用此算法,可以解决大型、复杂运输网络中容量限制的结点很多时的最大流分配问题,此算法也为解决实际的运输问题提供了应用基础.

作者：寇玮华李宗平KOU Wei-hua LI Zong-ping 作者单位：西南交通大学,交通运输学院,成都,610031 刊名：交通运输工程与信息学报 ISTIC英文刊名：JOURNAL OF TRANSPORTATION ENGINEERING AND INFORMATION 年，卷(期)：2008 6(4) 分类号：V121 关键词：大型复杂运输网络最大流分配结点容量限制增流链 Ford-Fulkerson算法

★基于GABP算法的计算机复杂网络可靠性评估方法研究论文

★网络上最感人的语句语录

★南京市，养老保险，上班按最底的算法，自己五险一金要交多少？

★朋友圈感人的爱情语录热门推荐网络最火爆的一句话爱情