30pts,WA求调
查看原帖
30pts,WA求调
722054
Yhy001楼主2025/1/26 21:18
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20005,M=400005;
const ll INF=1e18;
struct MF {
  struct edge {
    int v, nxt; ll cap, flow;
  } e[M];

  int fir[N], cnt = 0;

  int n, S, T;
  ll maxflow = 0;
  int dep[N], cur[N];

  void init() {
    memset(fir, -1, sizeof fir);
    memset(dep, 0, sizeof dep);
    cnt = 0;
  }

  void addedge(int u, int v, ll w,ll w2) {
    e[cnt] = {v, fir[u], w, 0};
    fir[u] = cnt++;
    e[cnt] = {u, fir[v], w2, 0};
    fir[v] = cnt++;
  }

  bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof(int) * (n + 1));
    dep[S] = 1;
    q.push(S);
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int i = fir[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if ((!dep[v]) && (e[i].cap > e[i].flow)) {
          dep[v] = dep[u] + 1;
          q.push(v);
          if(v==T) return 1;
        }
      }
    }
    return 0;
  }

  ll dfs(int u, ll flow) {
    if ((u == T) || (!flow)) return flow;

    ll ret = 0;
    for (int& i = cur[u]; ~i; i = e[i].nxt) {
      int v = e[i].v;
      ll d;
      if ((dep[v] == dep[u] + 1) &&(d = dfs(v, min(flow - ret, e[i].cap - e[i].flow)))) {
        ret += d;
        e[i].flow += d;
        e[i ^ 1].flow -= d;
        if (ret == flow) return ret;
      }
    }
    return ret;
  }

  void dinic() {
    while (bfs()) {
      memcpy(cur, fir, sizeof(int) * (n + 1));
      maxflow += dfs(S, INF);
    }
  }
} mf;
int u[200005],v[200005],w[200005];
int main(){
    int m;cin>>mf.n>>m;
    mf.init();
    for(int i=1;i<=m;i++) cin>>u[i]>>v[i]>>w[i];
    int l;cin>>mf.S>>mf.T>>l;
    for(int i=1;i<=m;i++) if(w[i]<l) mf.addedge(u[i],v[i],1,1);
    mf.dinic();
    ll ans=mf.maxflow;
    mf.init();
    for(int i=1;i<=m;i++) if(w[i]>l) mf.addedge(u[i],v[i],1,1);
    mf.dinic();
    cout<<mf.maxflow+ans;
}
2025/1/26 21:18
加载中...