VJ链接：https://vjudge.net/problem/HDU-1281
由题目描述中的“不在这些格子上放车，也可以保证尽量多的“车”被放下。”
可以联想到这句话本意即为这条路存在于在增广路中，属于“翻转”增广路之前存在的匹配。
（图示增广路中箭头所指就是一条“非重要边‘）（土丑土丑的手绘。） 想到了将行与列做最大匹配（一个车攻击范围为该行和该列嘛），但是没想到怎么判断“重要边”。
后来发现直接删边判断最大匹配有没有变小就可以了。。。。
匈牙利算法复杂度O（n*m），每个点都需要去寻找一次匹配，匹配过程最坏的情况就是全部边都要变，所以为n * m。
总复杂度为O(（n*m）^2）（第一次尝试计算复杂度也不知道对没。。不会算复杂度还挺麻烦的。。）
代码：
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,m,k;
int mp[111][111];
int vis[111],pei[111];
int road[MAXN<<1];
int dfs(int i)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]&&vis[j]==0)
{
vis[j]=1;
if(!pei[j]||dfs(pei[j]))
{
pei[j]=i;
return 1;
}
}
}
return 0;
}
int hungry()//
{
mem(pei,0);
int ans=0;
//求出原图的最大匹配
for(int i=1;i<=n;i++)
{
mem(vis,0);
ans+=dfs(i);
}
return ans;
}
int main()
{
int t=1;
while(~s3(n,m,k))
{
mem(mp,0);
for(int i=1,a,b;i<=k;i++)
{
s2(a,b);
mp[a][b]=1;
road[2*i-1]=a;
road[2*i]=b;
}
//
int ans=hungry();
//
int sum=0;
for(int i=1;i<=2*k;i+=2)
{
mp[road[i]][road[i+1]]=0;
int temp=hungry();
if(temp!=ans)
sum++;
mp[road[i]][road[i+1]]=1;
}
printf("Board %d have %d important blanks for %d chessmen.\n",t++,sum,ans);
}
return 0;
}
-
Swap
VJ链接：https://vjudge.net/problem/HDU-2819
问能不能通过交换，使主对角线全为一，可以发现如果满足题目条件，行和列存在一一对应关系，
和上一题相似，棋盘中某格为1表示该行与该列可以匹配。
做一次最大匹配看等不等n，输出路径方面，匈牙利算法的match数组已经记录了路径。‘
手动模拟交换过程即可（第一次遇见要输出路径的，终于理顺了点怎么输出，，，），比如，
要达到交换某两行的目的，只要交换match数组即可，如此样例中，
对于原棋盘，第1列要去第4列，第3列要去第1列，
交换1，3列之后，原本的第3列变成了第1列，那么此时棋盘中第1列不必交换（第一列匹配成功），
原本的第1列变成了第3列，此时他还是要去第4列，那么此时match[3]（=4）应为原本的match[1]（=4）（交换后的第三列即为原本的第一列）
match[1]同理。
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n;
int mp[111][111];
int vis[111],pei[111];
int dfs(int i)
{
for(int j=1; j<=n; j++)
{
if(mp[i][j]&&vis[j]==0)
{
vis[j]=1;
if(!pei[j]||dfs(pei[j]))
{
pei[j]=i;
return 1;
}
}
}
return 0;
}
int hungry()
{
mem(pei,0);
int ans=0;
for(int i=1; i<=n; i++)
mem(vis,0),ans+=dfs(i);
return ans;
}
int main()
{
while(~s1(n))
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
s1(mp[i][j]);
int ans=hungry();
if(ans!=n) printf("-1\n");
else
{
// for(int k=1; k<=n; k++)
// printf("pei[%d]=%d\n",k,pei[k]);
int num = 0,a[110], b[110];
for (int i = 1; i <= n; i++)
{
if (i == pei[i]) continue;
for (int j = 1; j <= n; j++)
{
if (i ==pei[j])
{
a[num]=i;b[num++]=j;
swap(pei[i],pei[j]);
// printf("after swap %d and %d:\n",i,j);
break;
}
}
// for(int k=1; k<=n; k++)
// printf("pei[%d]=%d\n",k,pei[k]);
}
printf("%d\n",num);
for (int i=0;i<num;i++)
printf("C %d %d\n",a[i],b[i]);
}
}
return 0;
} -
Rain on your Parade
VJ链接：https://vjudge.net/problem/HDU-2389
建图，OK，匈牙利，OK，提交，T。
匈牙利算法复杂度n*m，这里n是3000，m最大3000*3000，n*m的时间就炸掉了。。。
第一次知道还有HK算法，大概看了一下原理，以后补HK，先抄板（危险发言）。
京公网安备 11010502036488号