結果

問題 No.654 Air E869120
ユーザー vjudge1
提出日時 2025-05-29 16:35:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,927 bytes
コンパイル時間 1,838 ms
コンパイル使用メモリ 176,688 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-29 16:35:41
合計ジャッジ時間 3,931 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 29 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #include<bits/stdc++.h>
// using namespace std;
// #define int long long
// const int inf = 1e18;
// int n, m, d;
// int u[1005], v[1005], p[1005], q[1005], w[1005];
// struct edge{
//     int to, w, op;
// };
// vector<edge>t[2005];
// int dis[2005], z[2005];
// pair<int, int> pre[2005];
// void add(int u, int v, int w){
//     auto x = edge{v, w, t[v].size()}, y = edge{u, 0, t[u].size()};
//     t[u].emplace_back(x);
//     t[v].emplace_back(y);
// }
// bool bfs(){
//     for(int i = 0; i <= m * 2 + 1; i++)dis[i] = 0;
//     dis[0] = 1;
//     queue<int> q;
//     q.emplace(0);
//     while(!q.empty()){
//         int p = q.front();
//         q.pop();
//         for(auto [to, w, op] : t[p]){
//             if(w && !dis[to]){
//                 dis[to] = dis[p] + 1;
//                 q.emplace(to);
//             }
//         }
//     }
//     return !!dis[m * 2 + 1];
// }
// int dfs(int now, int w){
//     if(w == 0 || now == m * 2 + 1)return w;
//     int s = 0;
//     // z[now] = 0;
//     // while(z[now] < t[now].size()){
//     //     auto &[to, v, op] = t[now][z[now]];
//     for(auto &[to, v, op] : t[now]){
//         if(dis[to] == dis[now] + 1 && w);
//         else{
//             // z[now]++;
//             continue;
//         }
//         int res = dfs(to, min(w-s, v));
//         s += res;
//         v -= res;
//         t[to][op].w += res;
//         // if(s == w)break;
//         // z[now]++;
//     }
//     return s;
// }
// signed main(){
//     // freopen("travel.in", "r", stdin);
//     // freopen("travel.out", "w", stdout);
//     ios::sync_with_stdio(0);
//     cin.tie(0);cout.tie(0);
//     cin >> n >> m >> d;
//     for(int i = 1; i <= m; i++){
//         cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i];
//         add(i * 2  - 1, i * 2, w[i]);
//         q[i] += d;
//     }
//     for(int i = 1; i <= n; i++){
//         vector<pair<int, int> > vec;
//         for(int j = 1; j <= m; j++){
//             if(u[j] == i)vec.emplace_back(p[j], j * 2 - 1);
//             if(v[j] == i)vec.emplace_back(q[j], j * 2);
//         }
//         if(i == 1)vec.emplace_back(-inf, 0);
//         if(i == n)vec.emplace_back(inf, m * 2 + 1);
//         sort(vec.begin(), vec.end());
//         for(int j = 1; j < vec.size(); j++){
//             add(vec[j-1].second, vec[j].second, inf);
//         }
//     }
//     int ans = 0;
//     while(bfs()){
//         // memset(z, 0, sizeof(z));
//         ans += dfs(0, inf);
//     }
//     cout << ans << '\n';
//     return 0;
// }

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int inf = 1e18, N = 6e3+50;
int n, m, d;
struct MF {
  struct edge {
    int v, nxt, cap, flow;
  } e[N];

  int fir[N], cnt = 0;

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

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

  void addedge(int u, int v, int w) {
    e[cnt] = {v, fir[u], w, 0};
    fir[u] = cnt++;
    e[cnt] = {u, fir[v], 0, 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);
        }
      }
    }
    return dep[T];
  }

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

    int ret = 0;
    for (int& i = cur[u]; ~i; i = e[i].nxt) {
      int v = e[i].v, 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[N], v[N], p[N], q[N], w[N];
signed main(){
    // freopen("travel.in", "r", stdin);
    // freopen("travel.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> d;
    mf.n = m*2+1;
    mf.S = 0, mf.T = m*2+1;
    mf.init();
    for(int i = 1; i <= m; i++){
        cin >> u[i] >> v[i] >> p[i] >> q[i] >> w[i];
        mf.addedge(i * 2 - 1, i * 2, w[i]);
        q[i] += d;
    }
    for(int i = 1; i <= n; i++){
        vector<pair<int, int> > vec;
        for(int j = 1; j <= m; j++){
            if(u[j] == i)vec.emplace_back(p[j], j * 2 - 1);
            if(v[j] == i)vec.emplace_back(q[j], j * 2);
        }
        if(i == 1)vec.emplace_back(-inf, 0);
        if(i == n)vec.emplace_back(inf, m * 2 + 1);
        sort(vec.begin(), vec.end());
        for(int j = 1; j < vec.size(); j++){
            mf.addedge(vec[j-1].second, vec[j].second, inf);
        }
    }
    mf.dinic();
    cout << mf.maxflow << '\n';
    return 0;
}
0