2020-2021:teams:legal_string:jxm2001:图论_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:图论_2 [2020/07/20 10:32] jxm2001 |
2020-2021:teams:legal_string:jxm2001:图论_2 [2021/08/15 16:45] (当前版本) jxm2001 [一般图最大匹配] |
||
|---|---|---|---|
| 行 222: | 行 222: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <iostream> | ||
| - | #include <cstdio> | ||
| - | #include <cstdlib> | ||
| - | #include <algorithm> | ||
| - | #include <string> | ||
| - | #include <sstream> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <cmath> | ||
| - | #include <vector> | ||
| - | #include <set> | ||
| - | #include <map> | ||
| - | #include <stack> | ||
| - | #include <queue> | ||
| - | #include <ctime> | ||
| - | #include <cassert> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | #define mem(a,b) memset(a,b,sizeof(a)) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline LL read_LL(){ | ||
| - | LL t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline char get_char(){ | ||
| - | char c=getchar(); | ||
| - | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
| - | return c; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=505,MAXM=1505,Inf=0x7fffffff; | const int MAXN=505,MAXM=1505,Inf=0x7fffffff; | ||
| struct Edge{ | struct Edge{ | ||
| 行 575: | 行 528: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <iostream> | ||
| - | #include <cstdio> | ||
| - | #include <cstdlib> | ||
| - | #include <algorithm> | ||
| - | #include <string> | ||
| - | #include <sstream> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <cmath> | ||
| - | #include <vector> | ||
| - | #include <set> | ||
| - | #include <map> | ||
| - | #include <stack> | ||
| - | #include <queue> | ||
| - | #include <ctime> | ||
| - | #include <cassert> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | #define mem(a,b) memset(a,b,sizeof(a)) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline LL read_LL(){ | ||
| - | LL t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline char get_char(){ | ||
| - | char c=getchar(); | ||
| - | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
| - | return c; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=55,MAXM=105,Inf=1e9; | const int MAXN=55,MAXM=105,Inf=1e9; | ||
| struct Edge{ | struct Edge{ | ||
| 行 836: | 行 742: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <iostream> | ||
| - | #include <cstdio> | ||
| - | #include <cstdlib> | ||
| - | #include <algorithm> | ||
| - | #include <string> | ||
| - | #include <sstream> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <cmath> | ||
| - | #include <vector> | ||
| - | #include <set> | ||
| - | #include <map> | ||
| - | #include <stack> | ||
| - | #include <queue> | ||
| - | #include <ctime> | ||
| - | #include <cassert> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | #define mem(a,b) memset(a,b,sizeof(a)) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+c-48;c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline LL read_LL(){ | ||
| - | LL t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+c-48;c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline char get_char(){ | ||
| - | char c=getchar(); | ||
| - | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
| - | return c; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=2005,MAXM=2e5+5,Inf=0x7fffffff; | const int MAXN=2005,MAXM=2e5+5,Inf=0x7fffffff; | ||
| struct Edge{ | struct Edge{ | ||
| 行 1071: | 行 930: | ||
| 首先最小顶点覆盖数不小于二分图的最大匹配数，否则无法覆盖匹配边。 | 首先最小顶点覆盖数不小于二分图的最大匹配数，否则无法覆盖匹配边。 | ||
| - | 另一方面考虑某个二分图的最大匹配，易知任意两个非匹配点间不连边，否则与最大匹配定义矛盾。 | + | 另一方面考虑某个二分图的最大匹配，对所有左部的未配点，跑交替路，同时标记路径上的所有点。 |
| - | 同时对一个匹配边的两个端点，最多有一个端点与非匹配点有连边，否则若两个端点都与其他非匹配点有连边将构成增广路。 | + | 最后选取所有未标记的左部点和被标记的右部点。 |
| - | 考虑取所有匹配边中与非匹配点有连边的点，则得到一个顶点覆盖，故最小顶点覆盖数不大于二分图的最大匹配数。证毕。 | + | 首先可以知道选取的点一定是已配点。因为所有左部的未配点会被作为起点标记，而右部的未配点一定不会被标记，否则产生增广路。 |
| + | |||
| + | 然后每条匹配边要么两端点同时被标记，要么两端点同时未被标记，因为只要到达右部已配点，一定会沿已配边到达左部已配点。 | ||
| + | |||
| + | 所以所选点数恰好为匹配边数，且已配边一定被覆盖。 | ||
| + | |||
| + | 同时不存在某条未配边左部点被标记且右部点未被标记。因为如果该边左端点被标记，则左端点一定会走未配边，固右端点被标记。 | ||
| + | |||
| + | 所以选取点构成点覆盖，即最小顶点覆盖数不大于二分图的最大匹配数。证毕。 | ||
| === 性质二 === | === 性质二 === | ||
| 行 1297: | 行 1164: | ||
| 所以可以考虑先将奇环缩为一个点，并使用并查集维护。 | 所以可以考虑先将奇环缩为一个点，并使用并查集维护。 | ||
| - | 具体算法仅改出代码和部分注释供参考。 | + | 具体算法仅给出代码和部分注释供参考。 |
| 时间复杂度 $O(n^2log n+nm)$。 | 时间复杂度 $O(n^2log n+nm)$。 | ||
| 行 1403: | 行 1270: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| - | #include <iostream> | ||
| - | #include <cstdio> | ||
| - | #include <cstdlib> | ||
| - | #include <algorithm> | ||
| - | #include <string> | ||
| - | #include <sstream> | ||
| - | #include <cstring> | ||
| - | #include <cctype> | ||
| - | #include <cmath> | ||
| - | #include <vector> | ||
| - | #include <set> | ||
| - | #include <map> | ||
| - | #include <stack> | ||
| - | #include <queue> | ||
| - | #include <ctime> | ||
| - | #include <cassert> | ||
| - | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| - | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| - | #define mem(a,b) memset(a,b,sizeof(a)) | ||
| - | using namespace std; | ||
| - | typedef long long LL; | ||
| - | inline int read_int(){ | ||
| - | int t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline LL read_LL(){ | ||
| - | LL t=0;bool sign=false;char c=getchar(); | ||
| - | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| - | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| - | return sign?-t:t; | ||
| - | } | ||
| - | inline char get_char(){ | ||
| - | char c=getchar(); | ||
| - | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
| - | return c; | ||
| - | } | ||
| - | inline void write(LL x){ | ||
| - | register char c[21],len=0; | ||
| - | if(!x)return putchar('0'),void(); | ||
| - | if(x<0)x=-x,putchar('-'); | ||
| - | while(x)c[++len]=x%10,x/=10; | ||
| - | while(len)putchar(c[len--]+48); | ||
| - | } | ||
| - | inline void space(LL x){write(x),putchar(' ');} | ||
| - | inline void enter(LL x){write(x),putchar('\n');} | ||
| const int MAXN=305,MAXM=500; | const int MAXN=305,MAXM=500; | ||
| struct Edge{ | struct Edge{ | ||
2020-2021/teams/legal_string/jxm2001/图论_2.1595212339.txt.gz · 最后更改: 2020/07/20 10:32 由 jxm2001
