POJ - 1459 Power Network 最大流模版，有点意思的输入-白红宇的个人博客

POJ - 1459 Power Network 最大流模版，有点意思的输入

发布日期：2021-05-10 11:28:38 浏览次数：12 分类：精选文章

本文共 2138 字，大约阅读时间需要 7 分钟。

题目链接

题意

n个节点，有用电器，有发电站，有中转站，m条路线，有流量限制，求最大用电器功率

思路

不知道为什么一个最大流模板题题干这么绕人。。按m建图，s向发电站连边，权为发电量，用电器向t连边，权为最大功率，跑最大流

输入部分稍显麻烦，自己用的cin，看别人的博客学的c输入，挺巧妙的。

代码

#include
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
              #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define endl "\n"//#define int long longusing namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=1010; const int maxe=50010; int head[maxn],cnt; struct Edge{ int v; int w; int next; }edge[maxe]; int n,n1,n2,m,k,s,t; ll maxflow; int deep[maxn];//²ã¼¶Êý£¬ÆäÊµÓ¦¸ÃÊÇlevel int now[maxe];//µ±Ç°»¡ÓÅ»¯ void init(){ memset(head,-1,sizeof(head));//Çå¿ÕËùÓÐµã¶ÔÓ¦±ßµÄÁªÏµ cnt=0; maxflow=0; return ; } void add(int u,int v,int w){ // cout<
             <<" "<
              
               <<" "<
               
                <

q; q.push(s);deep[s] = 0;now[s] = head[s];//Ò»Ð©³õÊ¼»¯ while(q.size()){ int x = q.front();q.pop(); for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].v; if(edge[i].w>0&&deep[y]==inf){ //Ã»×ß¹ýÇÒÊ£ÓàÈÝÁ¿´óÓÚ0 q.push(y); now[y]=head[y];//ÏÈ³õÊ¼»¯£¬ÔÝÊ±¶¼Ò»Ñù deep[y]=deep[x]+1; if(y==t) return 1;//ÕÒµ½ÁË } } } return 0; }//flowÊÇÕûÌõÔö¹ãÂ·¶Ô×î´óÁ÷µÄ¹±Ï×£¬restÊÇµ±Ç°×îÐ¡Ê£ÓàÈÝÁ¿£¬ÓÃrestÈ¥¸üÐÂflow ll dfs(int x,int flow){ //ÔÚµ±Ç°·Ö²ãÍ¼ÉÏÔö¹ã if(x==t) return flow; ll ans = 0,k,i; for(i=now[x];i!=-1&&flow;i=edge[i].next){ now[x]=i;//µ±Ç°»¡ÓÅ»¯£¨±ÜÃâÖØ¸´±éÀú´Óx³ö·¢µÄ²»¿ÉÍØÕ¹µÄ±ß£© int y=edge[i].v; if(edge[i].w>0&&(deep[y]==deep[x]+1)){ //±ØÐëÊÇÏÂÒ»²ã²¢ÇÒÊ£ÓàÈÝÁ¿´óÓÚ0 k=dfs(y,min(flow,edge[i].w));//È¡×îÐ¡ if(!k) deep[y]=inf;//¼ôÖ¦£¬È¥µôÔö¹ãÍê±ÏµÄµã edge[i].w-=k;//»ØËÝÊ±¸üÐÂ edge[i^1].w+=k;//³É¶Ô±ä»» ans+=k; flow-=k; } } return ans; } void dinic(){ while(bfs()) maxflow+=dfs(s,inf); } int main(){ while(scanf("%d%d%d%d",&n,&n1,&n2,&m)==4){ init(); s=n+5,t=s+1; while(m--){ int u,v,w; while(getchar()!='('); scanf("%d%*c%d%*c%d",&u,&v,&w); add(u,v,w); add(v,u,0); } while(n1--){ int u,w; while(getchar()!='('); scanf("%d%*c%d",&u,&w); add(s,u,w); add(u,s,0); } while(n2--){ int u,w; while(getchar()!='('); scanf("%d%*c%d",&u,&w); add(u,t,w); add(t,u,0); } dinic(); printf("%d\n",maxflow); } return 0; }

上一篇：HDU - 4280 Island Transport 双向图最大流

下一篇：POJ - 2516 Minimum Cost 费用流，拆图

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目链接

题意

思路

代码

发表评论

最新留言

关于作者

推荐文章