2017 ACM-ICPC 亚洲区（青岛赛区）网络赛 1009-白红宇

2017 ACM-ICPC 亚洲区（青岛赛区）网络赛 1009

阅读量：7024 次

发布时间：2019-06-28

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

#include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     using namespace std;typedef long long ll;const double eps=1e-6;const int INF=0x3f3f3f3f;const int maxn=9876;const double PI=acos(-1.0);int head[maxn],path[maxn],vis[maxn];int tt;int ans,flag,cnt, n,m,s,t;;struct Edge{ int from,to,cap,next;}e[maxn];void init(){ cnt=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path));}void add(int u,int v,int w){ e[cnt].from=u; e[cnt].to=v; e[cnt].cap=w; e[cnt].next=head[u]; head[u]=cnt++;}int bfs(){ queue
                     
                       q; q.push(s); vis[s]=1; path[s]=-1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(e[i].cap>0&&!vis[v]) { path[v]=i; vis[v]=1; if(v == t) return 1; q.push(v); } } } return 0;}int EdmondsKarp(){ int Flow=0; int flow,i; while(bfs()) { memset(vis,0,sizeof(vis)); i=path[t]; flow=INF; while(i!=-1) { flow=min(flow,e[i].cap); i=path[e[i].from]; } i=path[t]; while(i!=-1) { e[i].cap-=flow; e[i^1].cap+=flow; i=path[e[i].from]; } Flow+=flow; } return Flow;}int main(){ scanf("%d",&tt); while(tt--) { scanf("%d%d",&n,&m); init(); scanf("%d%d",&s,&t); for(int i=0;i