Submission #3014644
Source Code Expand
#include<iostream> #include<string> #include<algorithm> #include<vector> #include<iomanip> #include<math.h> #include<complex> #include<queue> #include<deque> #include<stack> #include<map> #include<set> #include<bitset> using namespace std; #define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i ) #define rep(i,n) REP(i,0,n) typedef long long ll; typedef pair<int,int> pint; typedef pair<ll,int> pli; const int inf=1e9+7; const ll longinf=1LL<<60 ; const ll mod=1e9+7 ; int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ; struct edge{int to;int cap;int rev;}; struct Dinic{ private: int n; vector<vector<edge>> v; vector<int> dist,iter; public: Dinic(int sz):n(sz),v(sz),dist(sz),iter(sz){} void addedge(int from,int to,int cap){ int x=v[to].size(),y=v[from].size(); v[from].push_back({to,cap,x}); v[to].push_back({from,0,y}); } void bfs(int s){ fill(dist.begin(),dist.end(),-1); queue<int> q; dist[s]=0; q.push(s); while(q.size()){ int x=q.front();q.pop(); rep(i,v[x].size()){ edge &e=v[x][i]; if(e.cap>0&&dist[e.to]<0){ dist[e.to]=dist[x]+1; q.push(e.to); } } } } int dfs(int x,int t,int f){ if(x==t)return f; for(int& i=iter[x];i<(int)v[x].size();++i){ edge& e=v[x][i]; if(e.cap>0&&dist[x]<dist[e.to]){ int d=dfs(e.to,t,min(f,e.cap)); if(d>0){ e.cap-=d; v[e.to][e.rev].cap+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; while(1){ bfs(s); if(dist[t]<0)return flow; fill(iter.begin(),iter.end(),0); int f; while((f=dfs(s,t,inf)>0)flow+=f; } } }; int main(){ int h,w; cin>>h>>w; Dinic dn(h+w+2); string s[h]; rep(i,h){ cin>>s[i]; rep(j,w){ if(s[i][j]=='S'){ dn.addedge(h+w, i, inf); dn.addedge(h+w, h+j, inf); } if(s[i][j]=='T'){ dn.addedge(i,h+w+1, inf); dn.addedge(h+j,h+w+1, inf); } if(s[i][j]=='o'){ dn.addedge(i, h+j, 1); dn.addedge(h+j, i, 1); } } } int ans=dn.max_flow(h+w, h+w+1); cout<<(ans>=inf?-1:ans)<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Lotus Leaves |
User | tempura0224 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2706 Byte |
Status | CE |
Compile Error
./Main.cpp: In member function ‘int Dinic::max_flow(int, int)’: ./Main.cpp:80:37: error: expected ‘)’ before ‘flow’ while((f=dfs(s,t,inf)>0)flow+=f; ^