Submission #32759166

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;} // read
#define N 100
#define INF 0x3f3f3f3f
int n,m;
int a[N+10];
int b[N+10];
vector<int> p2[110]; // 双向关系
int S = 0;
int T = 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

#define N 100
#define INF 0x3f3f3f3f
int n,m;
int a[N+10];
int b[N+10];
vector<int> p2[110]; // 双向关系

int S = 0;
int T = 1;

// S,T,[2..101],[102...201][202..301][302..401]
//
int nodex(int x) {
  assert(x >=0 && x< 100);
  return 2+x;
}

int nodey(int y,int value) {
  assert(y >=0 && y< 100);
  assert(value >=1 && value <= 100);
  return 101 + y*100 + value;
}

class MinCut{
  int sz ;
  // TODO 优化成正反边下标
  vector<unordered_map<int,ll> > G; // {idx,weight}
  vector<int> d; // bfs 距离

public:
  MinCut(int n):sz(n){
    G = vector<unordered_map<int,ll> >(sz);
  }

  void path(int u,int v,ll w){
    G[u][v] += w;
  }

  int dfs(int u,int en, ll s){
    if (u == en)return s;
    for(auto [v,w]:G[u]){
      if(w == 0) continue;
      if(d[v] != d[u]+1) continue;
      int r = dfs(v,en,min(s,w));
      if(r){
        G[u][v] -= r;
        G[v][u] += r;
        return r;
      }
    }
    d[u] = 0; // 标记无效 替代vis
    return 0;
  }

  bool bfs(int st,int en){
    d = vector<int>(sz+10,-1);
    vector<int> q = {st};
    d[st] = 0;
    rep(i,0,q.size()){
      int u = q[i];
      for(auto [v,w]: G[u]){ // u -> v, weight =w
        if(d[v] != -1) continue;
        if(w == 0) continue;
        d[v] = d[u] +1;
        q.pb(v);
      }
    }
    return d[en] >= 0;
  }
  // 一次性计算
  ll calc(int st,int en){
    int ans = 0;
    while (bfs(st, en)) ans += dfs(st, en, INF);
    return ans;
  }
};

int main(){
  n = read();
  S = 0;
  T = 1;

  rep(i,0,n){
    a[i] = read();
    b[i] = read();
  }
  m = read();
  int ans = 0;
  // 预处理 和 建边
  rep(i,0,m){
    int x = read() - 1;
    int y = read() - 1;
    int minv = min(b[x],b[y]);
    ans += max(0,minv - a[x]);
    a[x] = max(a[x],minv);
    ans += max(0,minv - a[y]);
    a[y] = max(a[y],minv);

    p2[x].pb(y);
    p2[y].pb(x);
  }
  MinCut mc(20000);
  rep(i,0,n) {
    if(a[i] < b[i]){ // i in X
      mc.path(S,nodex(i),b[i] - a[i]);
      for(auto u:p2[i]){ // u in Y
        if(a[u] >= b[i]) continue;
        mc.path(nodex(i),nodey(u,b[i]-a[u]),INF);
      }
    }else{ // i in Y
      rep(j,1,101){
        mc.path(nodey(i,j),T,1);
        if(j > 1){
          mc.path(nodey(i,j),nodey(i,j-1),INF);
        }
      }
    }
  }
  printf("%lld\n",ans + mc.calc(S,T) );
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result