Luogu 3376 网络最大流

题目链接： https://www.luogu.org/problemnew/show/P3376

思路：

这道题数据范围较大，按照邻接矩阵的方法存边只能得70分。

还是先考虑求解，只是更换存边方法。

由于本人对掌握不是很好，于是就没敢用存边，听说很方便？

其实邻接矩阵比较好写，在存反向边和增广方面。

用邻接表其实也不难。

对于反向边，我们边号需要从0开始，也就是与平常不同，。

然后就可以用异或来做，因为0^1=1,1^1=0,2^1=3,3^1=2,......

然后增光的时候循环稍有不同，看代码吧。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
static const int MAXN=20050;
static const int MAXM=200050;
static const int INF=1<<30;
using namespace std;
struct Edge{
    int from,to,val,nextt;
}edge[MAXM];
int n,m,s,t,u,v,w,num,maxflow,head[MAXN],res[MAXN],father[MAXN];
queue<int> q;
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline void addedge(int u,int v,int w){
    edge[num].from=u;
    edge[num].to=v;
    edge[num].val=w;
    edge[num].nextt=head[u];
    head[u]=num++;
}
inline bool bfs(int s,int t){
    while(!q.empty()) q.pop();
    memset(res,0,sizeof(res));
    q.push(s);
    res[s]=INF;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=edge[i].nextt){
            int to=edge[i].to;
            if(res[to]==0&&edge[i].val){
                father[to]=i;
                res[to]=min(res[x],edge[i].val);
                q.push(to); 
            }
        }
        if(res[t]) return true;
    }
    return false;
}
inline int EK(int s,int t){
    while(1){
        if(!bfs(s,t)) break;
        for(int i=t;i!=s;i=edge[father[i]].from){
            edge[father[i]].val-=res[t];
            edge[father[i]^1].val+=res[t];
        }
        maxflow+=res[t];
    }
    return maxflow;
}
int main(){
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++){
        u=read();v=read();w=read();
        addedge(u,v,w);
        addedge(v,u,0);
    }
    printf("%d\n",EK(s,t));
    return 0;
}

之后会更新算法。