社区讨论

萌新刚学OI求助大佬

学术版参与者 5已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi7wf1ma
此快照首次捕获于
2025/11/21 04:43
4 个月前
此快照最后确认于
2025/11/21 04:43
4 个月前
查看原帖
P4311 士兵占领
代码为什么总是挂掉啊
思路明明是对的啊
求助大佬QAQ
CPP
#include<bits/stdc++.h>
#define Inf 0x7f7f7f7f
namespace fast_IO {
    const int IN_LEN=10000000,OUT_LEN=10000000;
    char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf;
    char *lastin=ibuf+IN_LEN;
    const char *lastout=ibuf+OUT_LEN-1;
    inline char getchar_() {
        if(ih==lastin)lastin=ibuf+fread(ibuf,1,IN_LEN,stdin),ih=ibuf;
        return (*ih++);
    } inline void putchar_(const char x) {
        if(ih==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;
        *oh++=x;
    } inline void flush() {
        fwrite(obuf, 1, oh - obuf, stdout);
    }
} 
using namespace fast_IO;
template <typename T> 
inline void Read(T&x) {
    char cu=getchar();
    x=0;
    bool fla=0;
    while(!isdigit(cu)) {
        if(cu=='-')fla=1;
        cu=getchar();
    }
    while(isdigit(cu))x=x*10+cu-'0',cu=getchar();
    if(fla)x=-x;
}
template <typename T> 
void printe(const T x) {
    if(x>=10)printe(x/10);
    putchar(x%10+'0');
}
template <typename T> 
inline void Write(const T x) {
    if(x<0)putchar('-'),printe(-x);
    else printe(x);
}
using namespace std;
int Sum,N,M,K,He,a,b,x,y,n,m,Start,End,Cnt,Used,Ans,Head[10010],Cur[10010],Dep[10010],To[200010],Next[200010],Val[200010];
char Map[110][110];
queue<int> Q;
void Add(int a,int b,int x){
    To[++Cnt]=b;
    Next[Cnt]=Head[a];
    Head[a]=Cnt;
    Val[Cnt]=x;
    To[++Cnt]=a;
    Next[Cnt]=Head[b];
    Head[b]=Cnt;
    Val[Cnt]=0;
}
bool Bfs(){
    memset(Dep,-1,sizeof(Dep));
    Dep[Start]=0;
    Q.push(Start);
    while(!Q.empty()){
        x=Q.front();
        Q.pop();
        for(int i=Head[x];i;i=Next[i]){
            if(Val[i]&&Dep[To[i]]==-1){
                Dep[To[i]]=Dep[x]+1;
                Q.push(To[i]);
            }
        }
    }
    return Dep[End]!=-1;
}
int Dfs(int x,int f){
    int w=0,Used=0;
    if(x==End){
        return f;
    }
    for(int &i=Cur[x];i;i=Next[i]){
        if(Dep[To[i]]==Dep[x]+1){
            w=f-Used;
            w=Dfs(To[i],min(Val[i],w));
            Val[i]-=w;
            Val[i^1]+=w;
            Used+=w;
            if(Used==f){
                return f;
            }
        }
    }
    if(!Used){
        Dep[x]=-1;
    }
    return Used;
}
void Dinic(){
    while(Bfs()){
        for(int i=1;i<=n+5;i++){
            Cur[i]=Head[i];
        }
        Ans+=Dfs(Start,Inf);
    }
}
int main() {
    Ans=0;
    Cnt=1;
    Read(N);
    Read(M);
    n=N*M+500;
    Read(K);
    Start=11000;
    End=11001;
    Sum=N*M-K;
    He=0;
	for(int i=1;i<=N;i++){
		Read(x);
		Add(Start,i+N*M,Sum-x);
		He+=x;
	}
	if(He>Sum){
		puts("JIONG!");
		return flush(),0;
	}
	He=0;
	for(int i=1;i<=M;i++){
		Read(x);
		Add(i+N*M+N,End,Sum-x);
		He+=x;
	}
	if(He>Sum){
		puts("JIONG!");
		return flush(),0;
	}
	for(int i=1;i<=K;i++){
		Read(x);
		Read(y);
		Map[x][y]=1;
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			if(Map[i][j]==0){
				Add(i+N*M,(i-1)*M+j,1);
				Add((i-1)*M+j,j+N*M+N,1);
			}
		}
	}
    Dinic();
    Write(Sum-Ans);
    return flush(),0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...