怪盗基德如约来到OIBH组织的大门，却发现OIBH组织的大门紧闭。而两旁两个小门则打开着。基德仔细观察之后发现了一些端倪：这两个小门门框上都装着红外线扫描器，能够对通过的物体作出反应。为了对付红外线扫描器，基德能够驱使他的滑翔翼高速飞行制造出N-1个幻影。但由于飞行时速度的不同，创造出的幻影速度也不同。两个幻影之间或幻影与基德之间若速度差距超过k，就会被红外线扫描器识别出来。因此这两个幻影（或幻影与基德）就不能从同一个门内进入。现在已知基德本身的速度和每个幻影的速度，请问基德能否带领所有幻影进入OIBH组织?
第1行三个整数n,v,k。v为基德本身的速度。n,k意义如题目所述。 第2行n-1个整数vi，表示n-1个幻影的速度。
Yes或No，表示基德能否带领所有幻影进入OIBH组织。
刚刚学二分图的知识，比较丑，见谅啦~(≧▽≦)/~啦啦啦
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,k,match[1000],ans=0; long long v[2000],left[1000],right[1000]; bool line[1000][1000],used[1000]; bool find(int x){ for(int i=1;i<=(n%2!=0?n/2+1:n/2);i++){ if(line[x][i]&&!used[i]){ used[i]=true; if(match[i]==0||find(match[i])){ match[i]=x; return true; } } } return false; } int main(){ //freopen("in.txt","r",stdin); //memset(used,0,sizeof(used)); memset(line,0,sizeof(line)); memset(match,0,sizeof(match)); scanf("%d %lld %d",&n,&v[1],&k); for(int i=2;i<=n;i++) scanf("%lld",&v[i]); for(int i=1;i<=n/2;i++){ left[i]=v[i]; right[i]=v[i+n/2]; } if(n%2!=0) right[n/2+1]=v[n]; for(int i=1;i<=n/2;i++) for(int j=1;j<=(n%2!=0?n/2+1:n/2);j++) if(abs(left[i]-right[j])<k) line[i][j]=true; for(int i=1;i<=n/2;i++){ memset(used,0,sizeof(used)); if(find(i)) ans++; } if(ans==n/2) puts("Yes"); else puts("No"); return 0; }转载于:https://www.cnblogs.com/leotan0321/p/6081397.html
