QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#41414 | #1943. Borders | nidhs | WA | 6ms | 12008kb | C++ | 2.9kb | 2022-07-30 13:39:17 | 2022-07-30 13:39:18 |
Judging History
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&∑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'