这题各种边界判断恶心死人
就是单调队列在每行求出最小的、能装进A*B方块里的花坛
然后再在刚刚求出的那个东西里面跑一遍竖着的单调队列
然后……边界调了一小时
做完这题我深刻地感觉到我又强了
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cctype> #include<queue> #include<vector> #define maxm 2000020 #define maxn 1010000 using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } inline int count(int i){ return i&1?i+1:i-1; } struct Edge{ int next,to,val; }edge[maxm*2]; int head[maxn],num; inline void addedge(int from,int to,int val){ edge[++num]=(Edge){head[from],to,val}; head[from]=num; } inline void add(int from,int to,int val){ addedge(from,to,val); addedge(to,from,0); } int dfn[maxn]; bool vis[maxn]; int Start,End; int last[maxm],tot; bool bfs(){ for(register int i=1;i<=tot;++i) vis[last[i]]=0; tot=0; dfn[Start]=1; vis[Start]=1; queue<int>q; q.push(Start); while(!q.empty()){ int from=q.front(); q.pop(); last[++tot]=from; for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(vis[to]||edge[i].val==0) continue; dfn[to]=dfn[from]+1; vis[to]=1; q.push(to); } } return vis[End]; } int dfs(int x,int val,int limit){ if(x<=10000&&x>limit) return 0; if(val==0||x==End) return val; int flow=0; vis[x]=1; last[++tot]=x; for(int i=head[x];i;i=edge[i].next){ int to=edge[i].to; if(edge[i].val==0||vis[to]||dfn[to]!=dfn[x]+1) continue; int now=dfs(to,min(val,edge[i].val),limit); edge[i].val-=now; edge[count(i)].val+=now; val-=now; flow+=now; if(val<=0) break; } if(flow!=val) dfn[x]=-1; return flow; } int maxflow(int limit){ int ans=0; while(bfs()){ for(register int i=1;i<=tot;++i) vis[last[i]]=0; tot=0; int now=dfs(Start,0x7fffffff,limit); if(!now) break; return now; } return ans; } int main(){ int n=read(); End=n+10000+1; for(int i=1;i<=n;++i){ int a=read(),b=read(); add(a,i+10000,1); add(b,i+10000,1); add(i+10000,End,1); } int ans; for(ans=1;;++ans){ add(Start,ans,1); if(maxflow(ans)==0) break; } printf("%d",ans-1); return 0; }