本文共 2969 字，大约阅读时间需要 9 分钟。
传送门：
题意：n*n的方格里有字符*和#，只能在字符#上放1*2的板子且不能相交，求最多能放多少个。
分析：直接给#字符编号，然后相邻的可以匹配，建边后无向图跑匈牙利算法，最后得到的最大匹配数/2。
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-6#define N 610#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PII pair using namespace std;int match[N],vis[N],n,m,cnt;int g[N][N],mat[N][N];char s[N][N];int dfs(int u){ for(int i=1;i<=cnt;i++) { if(!vis[i]&&g[u][i]) { vis[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return 1; } } } return 0;}int hungary(){ memset(match,-1,sizeof(match)); int ans=0; for(int i=1;i<=cnt;i++) { memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } return ans;}void judge(int i,int j){ if(j+1<=n&&mat[i][j+1]) g[mat[i][j]][mat[i][j+1]]=g[mat[i][j+1]][mat[i][j]]=1; if(i+1<=n&&mat[i+1][j]) g[mat[i][j]][mat[i+1][j]]=g[mat[i+1][j]][mat[i][j]]=1;}int main(){ int T,cas=1; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) if(s[i][j]=='#') mat[i][j]=++cnt; else mat[i][j]=0; } FILL(g,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mat[i][j])judge(i,j); int res=hungary(); printf("Case %d: %d\n",cas++,res/2); }}
题意：n*m的方格里有字符*和o，相邻的两个字符*可以连接，求覆盖完所有的*最少需要多少边。
分析：最少边覆盖所有点，就是最少边覆盖，最少边覆盖=总结点-最大匹配（双向图）/2。
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-6#define N 410#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PII pair using namespace std;int match[N],vis[N],n,m,cnt;int g[N][N],mat[N][N];char s[N][N];int dfs(int u){ for(int i=1;i<=cnt;i++) { if(!vis[i]&&g[u][i]) { vis[i]=1; if(match[i]==-1||dfs(match[i])) { match[i]=u; return 1; } } } return 0;}int hungary(){ memset(match,-1,sizeof(match)); int ans=0; for(int i=1;i<=cnt;i++) { memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } return ans;}void judge(int i,int j){ if(j+1<=m&&mat[i][j+1]) g[mat[i][j]][mat[i][j+1]]=g[mat[i][j+1]][mat[i][j]]=1; if(i+1<=n&&mat[i+1][j]) g[mat[i][j]][mat[i+1][j]]=g[mat[i+1][j]][mat[i][j]]=1;}int main(){ int T,cas=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) if(s[i][j]=='*') mat[i][j]=++cnt; else mat[i][j]=0; } FILL(g,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mat[i][j])judge(i,j); int res=hungary(); printf("%d\n",cnt-res/2); }}
转载于:https://www.cnblogs.com/lienus/p/4287110.html
