社区讨论
萌新刚学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 条回复,欢迎继续交流。
正在加载回复...