找不同

P3376 【模板】网络最大流

konyakest @ 2023-01-24 22:17:12

照着oi-wiki上写的，91pts，TLE on 9

code：

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
#define ckmax(a,b) a=max(a,b)
#define ckmin(a,b) a=min(a,b)

#define DEBUG

#ifdef DEBUG
template<typename T>void dbg(const T& t){cerr<<t<<endl;}
template<typename T,typename... Args>void dbg(const T& t,const Args&...r){cerr<<t<<",";dbg(r...);}
#define debug(...) {cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = ";dbg(__VA_ARGS__);}
#else
#define debug(...) 
#endif

#define int long long
const int maxn=250;

struct Edge{
    int x,y;
    long long c,f;
};

int n,m,s,t,x,y,z;

struct Dinic{
    vector<Edge> edge;
    vector<int> v[maxn];
    long long d[maxn],c[maxn];
    bool vis[maxn];

    void add(int x,int y,int c){
        edge.push_back({x,y,c,0});
        edge.push_back({y,x,0,0});
        v[x].push_back(edge.size()-2);
        v[y].push_back(edge.size()-1);
    }
    bool bfs(){
        memset(vis,0,sizeof vis);
        queue<int> q;
        q.push(s);
        d[s]=0,vis[s]=1;
        while(!q.empty()){
            int f=q.front();
            q.pop();
            for(auto i:v[f]){
                Edge& e=edge[i];
                if(!vis[e.y]&&e.c>e.f){
                    vis[e.y]=1;
                    d[e.y]=d[f]+1;
                    q.push(e.y);
                }
            }
        }
        return vis[t];
    }
    long long dfs(int x,long long a){
        if(x==t||a==0) return a;
        long long flow=0,f=0;
        F(i,c[x],v[x].size()-1){
            Edge& e=edge[v[x][i]];
            if(d[x]+1==d[e.y]&&(f=dfs(e.y,min(a,e.c-e.f)))>0){
                e.f+=f;
                edge[v[x][i]^1].f-=f;
                flow+=f;
                a-=f;
                if(!a) break;
            }
        } 
        return flow;
    }
    long long maxflow(){
        long long f=0;
        while(bfs()){
            memset(c,0,sizeof c);
            f+=dfs(s,LLONG_MAX/3);
        }
        return f;
    }
}dinic;

signed main() { 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s>>t;
    F(i,1,m) cin>>x>>y>>z,dinic.add(x,y,z);
    cout<<dinic.maxflow()<<endl;
    return 0; 
}

by konyakest @ 2023-01-24 22:18:23

与以下代码仅变量定义不同：

#define maxn 250
#define INF 0x3f3f3f3f

struct Edge {
  int from, to, cap, flow;

  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct Dinic {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];
  int d[maxn], cur[maxn];
  bool vis[maxn];

  void init(int n) {
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
  }

  int DFS(int x, int a) {
    if (x == t || a == 0) return a;
    int flow = 0, f;
    for (int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i] ^ 1].flow -= f;
        flow += f;
        a -= f;
        if (a == 0) break;
      }
    }
    return flow;
  }

  int Maxflow(int s, int t) {
    this->s = s;
    this->t = t;
    int flow = 0;
    while (BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, INF);
    }
    return flow;
  }
};

by sprads @ 2023-01-24 22:26:27

区别其实挺大的，当前弧优化假了：

F(i,c[x],v[x].size()-1)

for (int& i = cur[x]; i < G[x].size(); i++)

差了个 &，cur[x] 没有把处理完的边跳过，复杂度假了

by konyakest @ 2023-01-24 22:29:56

@sprads 感谢！%%%，您tql