HDU 4185 Oil Skimming
//https://www.cnblogs.com/nanke/archive/2012/03/31/2427656.html
//用1*2的木板覆盖矩阵中的‘#’，（木板要覆盖的只能是‘#’），问最多能用几个木板覆盖
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3610,M=36002;
struct node{
int to,ne;
}e[M];
int n,m,i,x,y,ans,h[N],vis[N],mat[N],tot,ca,ha[602][602],sum1,sum2,
b[4][2]={{1,0},{0,1},{-1,0},{0,-1}},T,j,k;
char s[602][602];
bool dfs(int u){
for (int i=h[u],v;i;i=e[i].ne)
if (!vis[v=e[i].to]){
vis[v]=1;
if (!mat[v] || dfs(mat[v])){
mat[v]=u;
return 1;
}
}
return 0;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
tot=sum1=sum2=0;
memset(h,0,sizeof(h));
memset(mat,0,sizeof(mat));
for (i=0;i<n;i++){
scanf("%s",s[i]);
for (j=0;j<n;j++)
if (s[i][j]=='#'){
if ((i+j)&1) ha[i][j]=++sum1;
else ha[i][j]=++sum2;
}
}
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (s[i][j]=='#' && ((i+j)&1))
for (k=0;k<4;k++){
x=i+b[k][0],y=j+b[k][1];
if (0<=x && x<n && 0<=y && y<n && s[x][y]=='#') add(ha[i][j],ha[x][y]);
}
ans=0;
for (i=1;i<=sum1;i++){
memset(vis,0,sizeof(vis));
if (dfs(i)) ans++;
}
printf("Case %d: %d\n",++ca,ans);
}
}poj1469(hopcroft-karp算法)
//https://www.cnblogs.com/penseur/archive/2013/06/16/3138981.html
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=502,M=300002;
struct node{
int to,ne;
}e[M];
int dis,dx[N],dy[N],h[N],cx[N],cy[N],vis[N],nx,ny,i,k,x,T,tot;
queue<int>q;
bool bfs(){
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
dis=1e9;
while (!q.empty()) q.pop();
for (int i=1;i<=nx;i++)
if (cx[i]==-1) q.push(i),dx[i]=0;
while (!q.empty()){
int u=q.front();q.pop();
if (dx[u]>dis) break;
for (int i=h[u],v;i;i=e[i].ne)
if (dy[v=e[i].to]==-1){
dy[v]=dx[u]+1;
if (cy[v]==-1) dis=dy[v];
else dx[cy[v]]=dy[v]+1,q.push(cy[v]);
}
}
return dis<1e9;
}
int dfs(int u){
for (int i=h[u],v;i;i=e[i].ne)
if (!vis[v=e[i].to] && dy[v]==dx[u]+1){
vis[v]=1;
if (cy[v]!=-1 && dy[v]==dis) continue;
if (cy[v]==-1 || dfs(cy[v])){
cy[v]=u;cx[u]=v;
return 1;
}
}
return 0;
}
int hk(){
int res=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while (bfs()){
memset(vis,0,sizeof(vis));
for (int i=1;i<=nx;i++)
if (cx[i]==-1) res+=dfs(i);
}
return res;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
int main(){
scanf("%d",&T);
while (T--){
memset(h,0,sizeof(h));
tot=0;
scanf("%d%d",&nx,&ny);
for (i=1;i<=nx;i++){
scanf("%d",&k);
while (k--){
scanf("%d",&x);
add(i,x);
}
}
puts(hk()==nx?"YES":"NO");
}
}HDU 1507 Uncle Tom’s Inherited Land*
#include<cstdio>
#include<cstring>
using namespace std;
const int N=102,M=202;
struct node{
int to,ne;
}e[M];
int n,m,i,x,y,ans,h[N],vis[N],mat[N],tot,ha[102][102],sum1,sum2,
b[4][2]={{1,0},{0,1},{-1,0},{0,-1}},j,k,pre[N],num1[N],num2[N],cnt;
bool dfs(int u){
for (int i=h[u],v;i;i=e[i].ne)
if (!vis[v=e[i].to]){
vis[v]=1;
if (!mat[v] || dfs(mat[v])){
mat[v]=u;pre[u]=v;
return 1;
}
}
return 0;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
int main(){
while (~scanf("%d%d",&n,&m) && n){
scanf("%d",&k);
tot=sum1=sum2=0;
memset(ha,0,sizeof(ha));
memset(h,0,sizeof(h));
memset(mat,0,sizeof(mat));
memset(pre,0,sizeof(pre));
for (i=0;i<k;i++){
scanf("%d%d",&x,&y);x--;y--;
ha[x][y]=-1;
}
for (i=0;i<n;i++)
for (j=0;j<m;j++)
if (ha[i][j]!=-1){
if ((i+j)&1) ha[i][j]=++sum1,num1[sum1]=i*m+j;
else ha[i][j]=++sum2,num2[sum2]=i*m+j;
}
for (i=0;i<n;i++)
for (j=0;j<m;j++)
if (ha[i][j]!=-1 && ((i+j)&1))
for (k=0;k<4;k++){
x=i+b[k][0],y=j+b[k][1];
if (0<=x && x<n && 0<=y && y<m && ha[x][y]!=-1) add(ha[i][j],ha[x][y]);
}
ans=0;
for (i=1;i<=sum1;i++){
memset(vis,0,sizeof(vis));
if (dfs(i)) ans++;
}
printf("%d\n",ans);
cnt=0;
for (i=1;cnt<ans;i++)
if (pre[i]) cnt++,printf("(%d,%d)--(%d,%d)\n",
num1[i]/m+1,num1[i]%m+1,num2[pre[i]]/m+1,num2[pre[i]]%m+1);
puts("");
}
}ZOJ1654-Place the Robots
/*https://blog.csdn.net/u014141559/article/details/44409255 在空地上放置尽可能多机器人，机器人朝上下左右4个方向发射子弹，子弹能穿过草地，但不能穿过墙， 两个机器人之间的子弹要保证互不干扰，求所能放置的机器人的最大个数*/
#include<cstdio>
#include<cstring>
using namespace std;
#define M(a) memset(a,0,sizeof(a))
const int N=2502;
struct node{
int to,ne;
}e[N];
int n,m,i,ans,h[N],vis[N],mat[N],tot,ca,fl,nx,ny,hx[52][52],hy[52][52],T,j;
char s[52][52];
int dfs(int u){
for (int i=h[u],v;i;i=e[i].ne)
if (!vis[v=e[i].to]){
vis[v]=1;
if (!mat[v] || dfs(mat[v])){
mat[v]=u;
return 1;
}
}
return 0;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&m);
tot=0;
M(hx);M(hy);M(h);M(mat);
nx=1;
for (i=0;i<n;i++){
scanf("%s",s[i]);
if (fl) fl=0,nx++;
for (j=0;j<m;j++)
if (s[i][j]=='o') fl=1,hx[i][j]=nx;
else if (s[i][j]=='#') nx++;
}
ny=1;
for (j=0;j<m;j++){
if (fl) fl=0,ny++;
for (i=0;i<n;i++)
if (s[i][j]=='o') fl=1,hy[i][j]=ny;
else if (s[i][j]=='#') ny++;
}
for (i=0;i<n;i++)
for (j=0;j<m;j++)
if (hx[i][j] && hy[i][j]) add(hx[i][j],hy[i][j]);
ans=0;
for (i=1;i<=nx;i++){
M(vis);
ans+=dfs(i);
}
printf("Case :%d\n%d\n",++ca,ans);
}
}HDU 4751 Divide Groups
/*https://blog.csdn.net/zhou_yujia/article/details/51188529 给出彼此认识的关系（不传递），问是否可以分成两部分使得两部分中都互相认识*/
#include<bits/stdc++.h>
using namespace std;
const int N=10002;
struct node{
int to,ne;
}e[N];
int n,mp[102][102],x,h[N],i,j,col[102],tot,fl;
bool dfs(int u,int fl){
col[u]=fl;
for (int i=h[u],v;i;i=e[i].ne){
if (col[v=e[i].to]==fl) return 0;
if (col[v]==-1 && !dfs(v,fl^1)) return 0;
}
return 1;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
int main(){
while (~scanf("%d",&n)){
tot=0;
memset(h,0,sizeof(h));
memset(mp,0,sizeof(mp));
for (i=0;i<n;i++)
while (scanf("%d",&x) && x) mp[i][x-1]=1;
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
if (!mp[i][j] || !mp[j][i]) add(i,j),add(j,i);
fl=1;
memset(col,-1,sizeof(col));
for (i=0;i<n && fl;i++)
if (col[i]==-1)
if (!dfs(i,0)) fl=0;
puts(fl?"YES":"NO");
}
}HDU 4685 Prince and Princess
/*此题弱化版poj1904题解：https://www.cnblogs.com/zhengguiping--9876/p/5676699.html hdu4685题解：https://blog.csdn.net/u014569598/article/details/42015415 有n个王子和m个公主，每个王子都会喜欢若干个公主，也就是王子只跟自己喜欢的公主结婚，公主跟谁结婚都行。 然后输出王子可能的结婚对象，必须保证王子与任意这些对象中的一个结婚，都不会影响到剩余的王子的配对数。*/
#include<bits/stdc++.h>
using namespace std;
#define M(a) memset(a,0,sizeof(a))
const int key=1000,N=2002;
struct node{
int to,ne;
}e[N*N>>1];
int dfn[N],low[N],mp[N][N],h[N],mat[N],i,tim,tot,top,st[N],inst[N],vis[N],ans[N],nn,k,m,n,
bel[N],scc,T,ca,cnt,x,j;
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
bool dfs(int u){
for (int i=h[u],v;i;i=e[i].ne)
if (!vis[v=e[i].to]){
vis[v]=1;
if (!mat[v] || dfs(mat[v])){
mat[v]=u;
return 1;
}
}
return 0;
}
int hungary(int n){
int ans=0;M(mat);
for (int i=1;i<=n;i++) M(vis),ans+=dfs(i);
return ans;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
st[top++]=u;inst[u]=1;
for (int i=h[u],v;i;i=e[i].ne)
if (!dfn[v=e[i].to]) tarjan(v),low[u]=min(low[u],low[v]);
else if (inst[v]) low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
int x;scc++;
do{
x=st[--top];
bel[x]=scc;
inst[x]=0;
}while (x!=u);
}
}
int main(){
scanf("%d",&T);
while (T--){
M(h);M(mp);tot=0;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++){
scanf("%d",&k);
while (k--){
scanf("%d",&x);
if (!mp[i][x]) mp[i][x]=1,add(i,x+key);
}
}
nn=n+m-hungary(n);
for (i=n+1;i<=nn;i++)
for (j=1;j<=nn;j++) mp[i][j]=1,add(i,j+key);
for (i=1;i<=n;i++)
for (j=m+1;j<=nn;j++) mp[i][j]=1,add(i,j+key);
hungary(nn);
M(dfn);M(inst);M(h);
tot=tim=scc=top=0;
for (i=1;i<=nn;i++)
if (mat[i+key]) add(i+nn,mat[i+key]);
for (i=1;i<=nn;i++)
for (j=1;j<=nn;j++)
if (mp[i][j]) add(i,j+nn);
for (i=1;i<=nn<<1;i++)
if (!dfn[i]) tarjan(i);
printf("Case #%d:\n",++ca);
for (i=1;i<=n;i++){
cnt=0;
for (j=1;j<=m;j++)
if (mp[i][j] && bel[i]==bel[j+nn]) ans[cnt++]=j;
printf("%d",cnt);
for (j=0;j<cnt;j++) printf(" %d",ans[j]);
puts("");
}
}
}HDU 3829 Cat VS Dog
题意：n个人，每个人有喜欢的动物和讨厌的动物，如果保留他喜欢的删去讨厌的他就很高兴，问最多让多少人高兴
题解：互斥关系建图，然后二分图最大匹配求最大独立点集
HDU 1150 Machine Schedule
题意：有k 个任务可以在 A 机器的某一种模式或者 B 机器上的某一种模式运行， 对于每一台机器不同模式之间需要切换，问完成 k 个任务需要至少切换多少次
题解：最小顶点覆盖
POJ 3692 Kindergarten
题意：求二分图最大团
题解：等于补图的最大独立集
京公网安备 11010502036488号