Submission #1679864

---

Source Code Expand

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>

using namespace std;
typedef long long LL;
const int maxn = 2000005;
const int maxm = 105;
const int inf = 1<<29;

int ehead[maxn],ecnt=1;
struct edge {
	int u,v,vol,next;
}edg[maxn];
void add(int u,int v,int w) {
	edg[++ecnt]=(edge){u,v,w,ehead[u]};
	ehead[u]=ecnt;
	edg[++ecnt]=(edge){v,u,0,ehead[v]};
	ehead[v]=ecnt;
}

char g[maxm][maxm];
int col[maxm],row[maxm];
int in[maxm][maxm];
int out[maxm][maxm];
int S,T,cnt,n,m;

namespace dinic {
	int que[maxn],head,tail,lab[maxn];
	bool bfs() {
		memset(lab,-1,cnt+1<<2);
		que[head=tail=0]=S;lab[S]=1;
		while (head<=tail) {
			int u=que[head++];
			for (int v,j=ehead[u];j;j=edg[j].next)
			if (edg[j].vol&&lab[v=edg[j].v]==-1)
				lab[v]=lab[u]+1,que[++tail]=v;
		}
		return lab[T]!=-1; 
	}
	int dfs(int u,int cur) {
		int res=0;
		if (u==T) return cur;
		for (int v,j=ehead[u];j&&res<cur;j=edg[j].next)
		if (edg[j].vol&&lab[v=edg[j].v]==lab[u]+1) {
			int tmp=dfs(v,min(cur-res,edg[j].vol));
			edg[j].vol-=tmp;edg[j^1].vol+=tmp;res+=tmp;
		}
		if (!res) lab[u]=-1;
		return res;
	}
	int main() {
		int res=0;
		while (bfs()&&res<inf) res+=dfs(S,inf);
		return res>=inf?-1:res;
	}
}
int main()
{
	#ifdef Amberframe
		freopen("arc074f.in","r",stdin);
		freopen("arc074f.out","w",stdout);
	#endif
	scanf("%d %d",&n,&m);S=++cnt;T=++cnt;
	for (int i=1;i<=n;i++) scanf("%s",g[i]+1);
	for (int i=1;i<=n;i++) row[i]=++cnt;
	for (int i=1;i<=m;i++) col[i]=++cnt;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	if (g[i][j]!='.') {
		in[i][j]=++cnt;out[i][j]=++cnt;
		if (g[i][j]=='S') add(S,out[i][j],inf);
		if (g[i][j]=='T') add(in[i][j],T,inf);
		add(out[i][j],row[i],inf);
		add(out[i][j],col[j],inf);
		add(row[i],in[i][j],inf);
		add(col[j],in[i][j],inf);
		add(in[i][j],out[i][j],1);
	}
	printf("%d",dinic::main());
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);S=++cnt;T=++cnt;
                      ^
./Main.cpp:67:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1;i<=n;i++) scanf("%s",g[i]+1);
                                           ^

Judge Result