怎么做好网站推广,全网营销推广方案,软件开发管理软件,钓鱼网页在线生成网站题干#xff1a;
小希和Gardon在玩一个游戏#xff1a;对一个N*M的棋盘#xff0c;在格子里放尽量多的一些国际象棋里面的“车”#xff0c;并且使得他们不能互相攻击#xff0c;这当然很简单#xff0c;但是Gardon限制了只有某些格子才可以放#xff0c;小希还是很轻松…题干
小希和Gardon在玩一个游戏对一个N*M的棋盘在格子里放尽量多的一些国际象棋里面的“车”并且使得他们不能互相攻击这当然很简单但是Gardon限制了只有某些格子才可以放小希还是很轻松的解决了这个问题见下图注意不能放车的地方不影响车的互相攻击。 所以现在Gardon想让小希来解决一个更难的问题在保证尽量多的“车”的前提下棋盘里有些格子是可以避开的也就是说不在这些格子上放车也可以保证尽量多的“车”被放下。但是某些格子若不放子就无法保证放尽量多的“车”这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点你能解决这个问题么 Input
输入包含多组数据 第一行有三个数N、M、K(1N,M100 1KN*M)表示了棋盘的高、宽以及可以放“车”的格子数目。接下来的K行描述了所有格子的信息每行两个数X和Y表示了这个格子在棋盘中的位置。
Output
对输入的每组数据按照如下格式输出 Board T have C important blanks for L chessmen.
Sample Input
3 3 4
1 2
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2
Sample Output
Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.
解题报告 line[i][j]在二分图中表示一条边在矩阵中就表示一个点了求最大匹配之后也就是说明每匹配一个行和列相当于是i行j列都已经用过了剩余的点不能在这行和这列放置了。
AC代码46ms代码
#includebits/stdc.husing namespace std;
const int MAX 100 5;
int x[MAX*MAX],y[MAX*MAX];
bool used[MAX];
int line[MAX][MAX],nxt[MAX];
int n,m,k;
bool find(int x) {for(int i 1; im; i) {if(used[i] 0 line[x][i]) {used[i]1;if(nxt[i] 0 || find(nxt[i])) {nxt[i] x;return 1;}}}return 0 ;
}
int match() {memset(nxt,0,sizeof nxt);int res 0;for(int i 1; in; i) {memset(used,0,sizeof used);if(find(i)) res;}return res;
}
int main()
{int iCase 0;while(~scanf(%d%d%d,n,m,k)) {memset(line,0,sizeof line);for(int i 1; ik; i) {scanf(%d%d,xi,yi);line[x[i]][y[i]]1;}int maxx match();int ans 0;for(int i 1; ik; i) {line[x[i]][y[i]]0;if(match() maxx) ans;line[x[i]][y[i]]1;}printf(Board %d have %d important blanks for %d chessmen.\n,iCase,ans,maxx);}return 0 ;}
AC代码20ms代码
#includebits/stdc.husing namespace std;
const int MAX 100 5;
int x[MAX*MAX],y[MAX*MAX];
bool used[MAX];
int line[MAX][MAX],nxt[MAX],xM[MAX],tmpxM[MAX];
int n,m,k;
bool find(int x) {for(int i 1; im; i) {if(used[i] 0 line[x][i]) {used[i]1;if(nxt[i] 0 || find(nxt[i])) {nxt[i] x;xM[x]i;return 1;}}}return 0 ;
}
int match() {memset(nxt,0,sizeof nxt);memset(xM,0,sizeof xM);//x的匹配 int res 0;for(int i 1; in; i) {memset(used,0,sizeof used);if(find(i)) res;}return res;
}
int main()
{int iCase 0;while(~scanf(%d%d%d,n,m,k)) {memset(line,0,sizeof line);for(int i 1; ik; i) {scanf(%d%d,xi,yi);line[x[i]][y[i]]1;}int maxx match();int ans 0;for(int i 1; in; i) tmpxM[i] xM[i];for(int i 1; in; i) {if(tmpxM[i] ! 0) {line[i][tmpxM[i]]0;if(match() maxx) ans;line[i][tmpxM[i]]1;}}printf(Board %d have %d important blanks for %d chessmen.\n,iCase,ans,maxx);}return 0 ;}
或者不对x弄对y弄就直接就可以了这里注意一定要把所有的matchline先赋值到一个数组中下面代码中的match数组就是nxt数组 也有的直接是Edge邻接表建图这样最后枚举删除顶点的时候直接就删除每一条边就可以了删边方法在总结博客里面写了很简单。那样跑出来也是0ms可能就优化在了Edge邻接表建图上因为枚举也是枚举了k个。
总之有两个可以优化的地方一个是减少枚举的点另一个是优化存图方式。任选一个优化都可以跑出来0ms