程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> ZOJ 2314 有上下界的網絡流

ZOJ 2314 有上下界的網絡流

編輯:關於C++

題意:給定m條邊和n個節點,每條邊最少的流量和最多的流量,保證每個節點的出入流量和相等,問可以形成嗎,可以則輸出每條邊的流量

思路:一道有上下界的網絡流,因為有下界,說明我們每條邊必須跑大於等於下界的流量,那我們可以轉化一下,將下界設為必要邊,也就是我們肯定會跑的邊,而且這道題是沒有源點和匯點的,所以我們要加這兩個點,而對於一條邊,a,b,low,high,我們a->b連的流量為high-low,a->T為low,S->b為low,跑最大流,如果滿流則方案成功,找邊的流量輸出即可,我感覺它為什麼正確呢,只是自己感覺的因為這東西好像沒法證明啊,我從源點出發,出發的每條邊都是下界,這就滿足了下界這個條件,而裡面沒有多添加邊的網絡也已經是上界減去下界的正常的網絡了,這樣我能從網絡裡將下界的流量傳輸到匯點,就能夠說明網絡的可行性,因為這樣只是調整了裡面的網絡的流量,並且裡面的網絡已經合法了,看著第二組樣例畫出來應該好理解一點.........說的自己都不是很清楚.......ZOJ的題有輸入組數T,我在VJ上做的沒有,加上就可以了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=210;
struct edge{
    int to,cap,rev;
    edge(int a,int b,int c){to=a;cap=b;rev=c;}
};
vectorG[maxn];
int level[maxn],iter[maxn];
void add_edge(int from,int to,int cap){
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1));
}
void bfs(int s){
    memset(level,-1,sizeof(level));
    queueque;level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v=que.front();que.pop();
        for(unsigned int i=0;i0&&level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f){
    if(v==t) return f;
    for(int &i=iter[v];i0&&level[v]0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t){
    int flow=0;
    while(1){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,inf))>0) flow+=f;
    }
}
int high[100010],num[100010][2];
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=-1){
        for(int i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved