結果

問題 No.119 旅行のツアーの問題
コンテスト
ユーザー nmnmnmnmnmnmnm
提出日時 2014-10-18 00:09:58
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,026 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 932 ms
コンパイル使用メモリ 91,024 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-21 10:42:46
合計ジャッジ時間 1,515 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 6 WA * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void MF::ae(int, int, int)’:
main.cpp:49:27: warning: narrowing conversion of ‘MF::g[t].std::vector<MF::Edge>::size()’ from ‘std::vector<MF::Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   49 |     Edge a = {t, g[t].size(), 0, cap};
      |                  ~~~~~~~~~^~
main.cpp:50:27: warning: narrowing conversion of ‘MF::g[s].std::vector<MF::Edge>::size()’ from ‘std::vector<MF::Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   50 |     Edge b = {s, g[s].size(), 0, cap};
      |                  ~~~~~~~~~^~

ソースコード

diff #
raw source code 

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
 
#define MOD 1000000009

#define MAX_NODE 82
#define INF 100000000

namespace MF{
  int nodes = MAX_NODE, src, dest;
  int dist[MAX_NODE], q[MAX_NODE], work[MAX_NODE];

  struct Edge {
    int to, rev;
    int f, cap;
  };

  vector<Edge> g[MAX_NODE];

  void ae(int s, int t, int cap){
    Edge a = {t, g[t].size(), 0, cap};
    Edge b = {s, g[s].size(), 0, cap};
    g[s].push_back(a);
    g[t].push_back(b);
  }

  int dinic_bfs() {
    memset(dist, -1, sizeof(dist));
    dist[src] = 0;
    int qt = 0;
    q[qt] = src;
    qt++;
    for(int i = 0; i < qt; i++) {
      int u = q[i];
      for(int j = 0; j < (int)g[u].size(); j++){
        Edge e = g[u][j];
        int v = e.to;
        if(dist[v] < 0 && e.f < e.cap){
          dist[v] = dist[u] + 1;
          q[qt] = v;
          qt++;
        }
      }
    }
    return dist[dest] >= 0 ? 1 : 0;
  }

  int dinic_dfs(int u, int f) {
    if(u == dest){
      return f;
    }
    for(int i = work[u]; i < (int)g[u].size(); i++){
      Edge &e = g[u][i];
      if(e.cap <= e.f){
        continue;
      }
      int v = e.to;
      if(dist[v] == dist[u]+1){
        int df = dinic_dfs(v, min(f, e.cap - e.f));
        if(df > 0){
          e.f += df;
          g[v][e.rev].f -= df;
          return df;
        }
      }
    }
    return 0;
  }

  int maxFlowDinic(int _src, int _dest) {
    src = _src;
    dest = _dest;
    int result = 0;
    while(dinic_bfs() == 1){
      memset(work, 0, sizeof(work));
      for(;;){
        int delta = dinic_dfs(src, INT_MAX);
        if(delta == 0)break;
        result += delta;
      }
    }
    return result;
  }
}

int main(){
  int sum = 0;
  int n;
  cin >> n;
  rep(i,0,n){
    int b,c;
    cin >> b >> c;
    MF::ae(2*n,i,b);
    MF::ae(i+n,2*n+1,c);
    MF::ae(i,i+n,INF);
    sum += b+c;
  }
  int m;
  cin >> m;
  rep(i,0,m){
    int d,e;
    cin >> d >> e;
    MF::ae(d,e+n,INF);
  }
  int f = MF::maxFlowDinic(2*n,2*n+1);
  cout << sum-f << endl;
  return 0;
}

/*
最小カットの問題です。
最小カットとわかればやるだけな問題のはずです。
最小カットのなんたるかがよくわかっていないので、
シンプルに問題をまとめることができませんでした、
このようなややこしい条件ですいません。
*/
0