传输数据

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/problem/show/1143

Description

机房里面有m台电脑，n台网线，每条网线都每秒中最多传送的数据量，现在需要你计算从标号为1的电脑传送数据到编号为m的电脑，问一秒内最多传送多少数据?

Input

第1行: 两个用空格分开的整数N(0≤N≤200)和 M(2≤M≤200)。N网线的数量，M是电脑的数量。

第二行到第N+1行: 每行有三个整数，Si，Ei 和 Ci。Si 和 Ei (1≤Si,Ei≤M) 指明电脑编号，数据从 Si 流向 Ei。Ci(0≤Ci≤10,000,000)是这条网线的最大容量。

Output

输出一个整数，即排水的最大流量。

Sample Input

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

Sample Output

HINT

题意

题解：

最大流裸题

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 10000#define eps 1e-9const int inf=0x7fffffff; //无限大//**************************************************************************************struct edge{ int to,cap,rev;};vector
                  
                    g[maxn];int level[maxn];int 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)); queue
                   
                     que; level[s]=0; que.push(s); while(!que.empty()) { int v=que.front(); que.pop(); for(int i=0;i
                    
                     0&&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];i
                     
                      0&&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 main(){ int n,m; while(cin>>n>>m) { for(int i=0;i<=m;i++) g[i].clear(); int a,b,c; for(int i=0;i
                       
                        >a>>b>>c; add_edge(a,b,c); } cout<
                        
                         <

转载地址：http://xwgdl.baihongyu.com/

你可能感兴趣的文章

联想大数据企业级分析平台（LEAP）通过数据中心联盟认证