QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#41414#1943. BordersnidhsWA 6ms12008kbC++2.9kb2022-07-30 13:39:172022-07-30 13:39:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-30 13:39:18]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:12008kb
  • [2022-07-30 13:39:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
typedef pair<int,int> pir;
string sstr[]={"NO\n","YES\n"};
const int N=200010;
int s,t,cnt=1;//从2开始,保证相反边只有低位不同 
int to[N],nxt[N],head[N],now[N];//now:当前弧优化 
ll wei[N],dis[N],ans,gnum;
void add(int u,int v,ll w)
{
	to[++cnt]=v;
	wei[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
	//反向边 
	to[++cnt]=u;
	wei[cnt]=0;
	nxt[cnt]=head[v];
	head[v]=cnt;
}
bool bfs()//分层 
{
	for(int i=0;i<=gnum;i++) dis[i]=inf;
	dis[s]=1;now[s]=head[s];
	queue<int> q;
	q.push(s);
	bool flag=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int j=to[i];
			if(wei[i]&&dis[j]==inf){
				q.push(j);
				now[j]=head[j];
				dis[j]=dis[x]+1;
				if(j==t) return 1;
			}
		}
	}
	return 0;
}
ll dfs(ll x,ll sum)//当前节点,以及当前节点的总流量 
{
	if(x==t) return sum;
	ll out=0;//out为结果
	for(int i=now[x];i&&sum;i=nxt[i]){
		now[x]=i;
		int j=to[i];
		if(wei[i]>0&&dis[j]==dis[x]+1){
			ll k=dfs(j,min(sum,wei[i]));//递归j
			if(k==0) dis[j]=inf;//剪枝,去除不可能的点
			wei[i]-=k;
			wei[i^1]+=k;
			out+=k;
			sum-=k;
		}
	}
	return out;//总流量 
}

int T,n,m;
int g[110][110];
int is[110][110];
int dfn[110][110];
int tot=0;
int bor[10010];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
set<int> vec[10010];
bool check(int i,int j)
{
	return i<=n&&i>=1&&j<=m&&j>=1;
}
void dfs1(int i,int j)
{
	dfn[i][j]=tot;
	if(is[i][j]) bor[tot]=1;
	int i1,j1;
	for(int k=0;k<4;k++){
		i1=i+dx[k];
		j1=j+dy[k];
		if(check(i1,j1)&&!dfn[i1][j1]&&g[i][j]==g[i1][j1]) dfs1(i1,j1);
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string str;
		cin>>str;
		for(int j=1;j<=m;j++){
			g[i][j]=str[j-1]-'0';
		}
	}
	for(int i=1;i<=n;i++) is[i][1]=is[i][m]=1;
	for(int j=1;j<=m;j++) is[1][j]=is[n][j]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!dfn[i][j]){
				tot++;
				dfs1(i,j);
			}
		}
	}
	int tans=0;
	for(int i=1;i<=tot;i++){
		if(bor[i]){
			tans++;
			continue;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<4;k++){
				int i1=i+dx[k];
				int j1=j+dy[k];
				if(check(i1,j1)&&!bor[dfn[i][j]]&&!bor[dfn[i1][j1]]&&dfn[i1][j1]!=dfn[i][j]){
					vec[dfn[i1][j1]].insert(dfn[i][j]);
					vec[dfn[i][j]].insert(dfn[i1][j1]);
					//cout<<"|||"<<dfn[i][j]<<' '<<dfn[i1][j1]<<'\n';
				}
			}
		}
	}
	s=tot+1,t=tot+2;
	int cnte=2;
	for(int i=1;i<=tot;i++){
		add(s,i,1);
		for(auto j:vec[i]){
			if(i<j){
				cnte++;
				add(i,cnte+tot,inf);
				add(j,cnte+tot,inf);
				add(cnte+tot,t,1);
			}
		}
	}
	gnum=tot+cnte;
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	cout<<tans+ans<<'\n';
}
/*
6 9
000000000
010001110
011101010
010101010
011101110
000000000

*/

详细

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 12008kb

input:

100 100
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:

10000

result:

wrong answer 1st lines differ - expected: '5198', found: '10000'