关于网络流,如果你觉得建图建对了,且板题过了,如以下程序:
#include<bits/stdc++.h>
#define cit const register unsigned
#define open ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)//,freopen("1.in","r",stdin),freopen("1.out","w",stdout)
using namespace std;constexpr unsigned N=1e4+1,p=924844033,inf=~0;
#define int register unsigned
#define ll long long
#define void inline void
#define cle(a) memset(a,0,sizeof a)
#define min(a,b) ((a)<(b)?(a):(b))
struct A{unsigned v,inv;unsigned ll w,f;};vector<A>a[N];unsigned sz[N];
void add(cit u,cit v,cit w){
a[u].emplace_back(A{v,sz[v],w,0});++sz[v];
a[v].emplace_back(A{u,sz[u],0,0});++sz[u];
}namespace ISAP{unsigned s,t,n,c[N],d[N],g[N];
inline unsigned ll dfs(cit u,cit ll r){if(u==t||!r)return r;
int ll b=0,v,w,f,h;for(;c[u]<sz[u];++c[u]){auto&e=a[u][c[u]];
v=e.v,w=e.w,f=e.f;if(d[u]==d[v]+1&&(h=dfs(v,min(r-b,w-f)))){
b+=h,e.f+=h,a[v][e.inv].f-=h;if(b==r||d[s]>=n)return b;}
}if(!(--g[d[u]]))d[s]=n;g[++d[u]]++;return b;}
inline unsigned ll aa(cit ts,cit tt,cit tn){int ll ans=0;cle(g),cle(d);
s=ts,t=tt,n=tn;while(d[s]<n)cle(c),ans+=dfs(s,inf);return ans;}}
signed main(){open;int n,m,s,t;cin>>n;m=(n<<1);s=0,t=n+m+1;
for(int i=1,x,y;i<=m;++i)cin>>x>>y,add(i,x+m,1),add(i,y+m,1);
for(int i=1;i<=m;++i)add(s,i,1);for(int i=1;i<=n;++i)add(i+m,t,2);
cout<<ISAP::aa(s,t,n);
}
此程序只有样例和第一组数据无法通过,不确定模板正确性,但能过板题,大数据均能 AC,原因是
ISAP::aa(const int s,const int t,const int n)
函数中,传入的参数 const int n 是节点个数,是正常结束算法的保证,如果不正确传入这个参数,会导致算法过早或过晚结束,但这种情况当且仅当 ISAP 算法被卡到接近上界时才会出现,一般这种情况并不多,且数据越大出现率越小,所以对于本题,小数据容易出锅,但 n 和实际节点个数相差只有 3 倍,所以 n 和实际上界相差不多,导致大数据没有把这个程序卡死,把最后一行改成:
cout<<ISAP::aa(s,t,t+1);
即可通过。
当然,即使你不用一个函数传入节点个数,而是用一个变量记录或者直接用 n 都不可避免的要注意节点个数的问题,这种 bug 很容易忽视,一定要加强重视
但实际上,根据这条记录,这种能卡死节点数量不正确的数据是存在的,所以加强数据是可行的,所以请求加强数据,并求构造这种数据的方法