結果

問題 No.1640 簡単な色塗り
コンテスト
ユーザー harurun
提出日時 2021-06-16 02:47:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,560 bytes
コンパイル時間 929 ms
コンパイル使用メモリ 79,256 KB
最終ジャッジ日時 2025-01-22 08:28:19
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 14 WA * 14 RE * 2 TLE * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:11:1: warning: ‘typedef’ was ignored in this declaration
   11 | typedef struct edge3{
      | ^~~~~~~
main.cpp: In member function ‘void FordFulkerson::add_edge(long long int, long long int, long long int)’:
main.cpp:28:48: warning: narrowing conversion of ‘(((FordFulkerson*)this)->FordFulkerson::G + ((sizetype)(((long unsigned int)to) * 24)))->std::vector<edge3>::size()’ from ‘std::vector<edge3>::size_type’ {aka ‘long unsigned int’} to ‘long long int’ [-Wnarrowing]
   28 |     G[from].push_back((edge3){to,cap,G[to].size()});
      |                                      ~~~~~~~~~~^~
main.cpp:29:50: warning: narrowing conversion of ‘((((FordFulkerson*)this)->FordFulkerson::G + ((sizetype)(((long unsigned int)from) * 24)))->std::vector<edge3>::size() - 1)’ from ‘std::vector<edge3>::size_type’ {aka ‘long unsigned int’} to ‘long long int’ [-Wnarrowing]
   29 |     G[to].push_back((edge3){from,0,G[from].size()-1});
      |                                    ~~~~~~~~~~~~~~^~
main.cpp: At global scope:
main.cpp:16:1: warning: ‘typedef’ was ignored in this declaration
   16 | typedef struct FordFulkerson{
      | ^~~~~~~

ソースコード

diff # 

//time測定用
//構築未実装
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
#define ll long long

typedef struct edge3{
  ll to,cap,rev;
};


typedef struct FordFulkerson{
  const ll INF=1000000000000000000;
  ll MAX_V;
  vector<edge3>* G;
  bool* used;
  FordFulkerson(){}
  FordFulkerson(ll max_v){
    G=new vector<edge3>[max_v];
    used=new bool[max_v];
    MAX_V=max_v;
  }
  void add_edge(ll from,ll to,ll cap){
    G[from].push_back((edge3){to,cap,G[to].size()});
    G[to].push_back((edge3){from,0,G[from].size()-1});
  }
  ll dfs(ll v,ll t,ll f){
    if(v==t)return f;
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
      edge3 &e=G[v][i];
      if(!used[e.to] && e.cap>0){
        ll d=dfs(e.to,t,min(f,e.cap));
        if(d>0){
          e.cap-=d;
          G[e.to][e.rev].cap+=d;
          return d;
        }
      }
    }
    return 0;
  }
  ll max_flow(ll s,ll t){
    ll flow=0;
    for(;;){
      fill(used,used+MAX_V,false);
      ll f=dfs(s,t,INF);
      if(f==0)return flow;
      flow+=f;
    }
    return flow;
  }
};

int main(){
  ll N,A,B;
  cin>>N;
  FordFulkerson F(200002);
  for(int i=0;i<N;i++){
    cin>>A>>B;
    A--;B--;
    F.add_edge(200000,i,1);
    F.add_edge(i,100000+A,1);
    if(A!=B)F.add_edge(i,100000+B,1);
    F.add_edge(100000+i,200001,1);
  }
  //cerr<<"edge added\n";
  ll cnt=F.max_flow(200000,200001);
  //cout<<cnt<<endl;
  if(cnt!=N){
    cout<<"No\n";
    return 0;
  }
  //ここから構築
  cout<<"Yes\n";
  return 0;
}
0