http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId&＃61;3726
将同在L范围内的棋子建立边&＃xff0c;然后做一般图的最大匹配(带花树算法)&＃xff0c;如果是完美匹配则输出YES&＃xff1b;否则输出NO。
如果有完美匹配的话&＃xff0c;顺着匹配拿掉棋子即可使后手赢。
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include 3 #include 4 #include 5 #include<string> 6 #include 7 #include<set> 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 const int maxn&＃61;500; 23 const int inf&＃61;0x3f3f3f3f; 24 const LL inf64&＃61;0x3f3f3f3f3f3f3f3fLL; 25 const double INF&＃61;1e30; 26 const double eps&＃61;1e-6; 27 28 /** 29 *一般图的最大基数匹配&＃xff1a;带花树算法 30 *输入&＃xff1a;g[][],n(输入从0到n-1,用addEdge()加边) 31 *输出&＃xff1a;gao()(最大匹配数),match[](匹配) 32 */ 33 //const int maxn&＃61;0; 34 struct Matching 35 { 36 deque<int> Q; 37 int n; 38 //g[i][j]存放关系图&＃xff1a;i,j是否有边,match[i]存放i所匹配的点 39 bool g[maxn][maxn],inque[maxn],inblossom[maxn],inpath[maxn]; 40 int match[maxn],pre[maxn],base[maxn]; 41 42 //找公共祖先 43 int findancestor(int u,int v) 44 { 45 memset(inpath,0,sizeof(inpath)); 46 while(1) 47 { 48 u&＃61;base[u]; 49 inpath[u]&＃61;true; 50 if(match[u]&＃61;&＃61;-1)break; 51 u&＃61;pre[match[u]]; 52 } 53 while(1) 54 { 55 v&＃61;base[v]; 56 if(inpath[v])return v; 57 v&＃61;pre[match[v]]; 58 } 59 } 60 61 //压缩花 62 void reset(int u,int anc) 63 { 64 while(u!&＃61;anc) 65 { 66 int v&＃61;match[u]; 67 inblossom[base[u]]&＃61;1; 68 inblossom[base[v]]&＃61;1; 69 v&＃61;pre[v]; 70 if(base[v]!&＃61;anc)pre[v]&＃61;match[u]; 71 u&＃61;v; 72 } 73 } 74 75 void contract(int u,int v,int n) 76 { 77 int anc&＃61;findancestor(u,v); 78 //SET(inblossom,0); 79 memset(inblossom,0,sizeof(inblossom)); 80 reset(u,anc); 81 reset(v,anc); 82 if(base[u]!&＃61;anc)pre[u]&＃61;v; 83 if(base[v]!&＃61;anc)pre[v]&＃61;u; 84 for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) 85 if(inblossom[base[i]]) 86 { 87 base[i]&＃61;anc; 88 if(!inque[i]) 89 { 90 Q.push_back(i); 91 inque[i]&＃61;1; 92 } 93 } 94 } 95 96 bool dfs(int S,int n) 97 { 98 for(int i&＃61;0; i<&＃61;n; i&＃43;&＃43;)pre[i]&＃61;-1,inque[i]&＃61;0,base[i]&＃61;i; 99 Q.clear();100 Q.push_back(S);101 inque[S]&＃61;1;102 while(!Q.empty())103 {104 int u&＃61;Q.front();105 Q.pop_front();106 for(int v&＃61;1; v<&＃61;n; v&＃43;&＃43;)107 {108 if(g[u][v]&&base[v]!&＃61;base[u]&&match[u]!&＃61;v)109 {110 if(v&＃61;&＃61;S||(match[v]!&＃61;-1&&pre[match[v]]!&＃61;-1))contract(u,v,n);111 else if(pre[v]&＃61;&＃61;-1)112 {113 pre[v]&＃61;u;114 if(match[v]!&＃61;-1)Q.push_back(match[v]),inque[match[v]]&＃61;1;115 else116 {117 u&＃61;v;118 while(u!&＃61;-1)119 {120 v&＃61;pre[u];121 int w&＃61;match[v];122 match[u]&＃61;v;123 match[v]&＃61;u;124 u&＃61;w;125 }126 return true;127 }128 }129 }130 }131 }132 return false;133 }134 135 void init(int n)136 {137 this->n &＃61; n;138 memset(match,-1,sizeof(match));139 memset(g,0,sizeof(g));140 }141 142 void addEdge(int a, int b)143 {144 &＃43;&＃43;a;145 &＃43;&＃43;b;146 g[a][b] &＃61; g[b][a] &＃61; 1;147 }148 149 int gao()150 {151 int ans &＃61; 0;152 for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)153 if (match[i] &＃61;&＃61; -1 && dfs(i, n))154 &＃43;&＃43;ans;155 return ans;156 }157 } match;158 159 int n,m,L;160 vectorint,int> > node;161 int dist(pair<int,int> A,pair<int,int> B)162 {163 return abs(A.first-B.first)&＃43;abs(A.second-B.second);164 }165 void init()166 {167 node.clear();168 match.init(m);169 }170 void input()171 {172 n&＃61;m;173 int u,v;174 while(m--)175 {176 scanf("%d%d",&u,&v);177 node.push_back(pair<int,int>(u,v));178 }179 scanf("%d",&L);180 pair<int,int> x,y;181 for(int i&＃61;0;i)182 {183 x&＃61;node[i];184 for(int j&＃61;0;j)185 {186 if(i&＃61;&＃61;j) continue;187 y&＃61;node[j];188 if(dist(x,y)<&＃61;L) match.addEdge(i,j);189 }190 }191 }192 void solve()193 {194 if(match.gao()*2&＃61;&＃61;n) puts("YES");195 else puts("NO");196 }197 int main()198 {199 // std::ios_base::sync_with_stdio(false);200 // freopen("in.cpp","r",stdin);201 while(~scanf("%d",&m))202 {203 init();204 input();205 solve();206 }207 return 0;208 }
转:https://www.cnblogs.com/xysmlx/p/3273249.html
京公网安备 11010802041100号