POJ – Page 2 – hahaschool

POJ 3083 Children of the Candy Corn

September 11, 20152015-09-11hahaschoolOne Comment

题意

对于一个入口和出口都在边界的迷宫，有两种一定能保证走出迷宫的方案，想象你自己站在迷宫的入口，你可以一直让左手扶着墙，贴着墙走，这样最后一定会走到终点。你也可以一直让右手扶着墙，贴着墙走，最终也一定会到达终点。现在要你模拟这两种策略，分别输出这样走要经历的步数，同时再算出不限于上述策略的走出迷宫的最短路方案。

思路

对于最短路，只要使用常规的BFS就可以解决。难点在于如何模拟左手扶墙和右手扶墙。如果是以左手扶墙来遍历迷宫的话，其实是相当于每一次都先尝试去走当前面朝方向的左边，若无法走，尝试直行，还不行的话，再尝试右行和上行。每一次行走，你要想想自己身处迷宫之中，并且根据你的行走动作来改变自己的朝向，模拟这个过程就是本题的难点。

有一种比较聪明的实现方式，就是把原来的行进向量(dir)，也当成朝向向量来用，往左行走相当于朝向向量左转，直行相当于无旋转，右行相当于向右旋转，下行相当于两次右旋。每一次前进时把旋转完的朝向向量当行进向量用就可以了，下一次还是按照上面所述的循环操作。

本题还有一个技巧，你只需要实现扶一边墙行走，因为从起点扶一边墙走到终点相当于从终点扶另一边墙走到起点，所以你在第一次行走完之后，只要交换起点终点的’S’和’E’，然后再执行一次从”原终点”到”原起点”的行走，就可以了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

char grid[42][42];

void counterClockwiseRotate(int &y,int &x){
    int t = -y;
    y = x;
    x = t;
}

void clockwiseRotate(int &y,int &x){
    int t = -x;
    x = y;
    y = t;
}



int follow(int inity,int initx){
    int cury = inity,curx = initx,step = 1;
    int diry = 0,dirx = -1;
    while (grid[cury][curx] != 'E') {
        for (int i = 0; i < 4; i++) {
            int nxty = cury + diry;
            int nxtx = curx + dirx;
            if (grid[nxty][nxtx] && grid[nxty][nxtx] != '#') {
                cury = nxty;
                curx = nxtx;
                step++;
                counterClockwiseRotate(diry, dirx);
                break;
            }
            clockwiseRotate(diry, dirx);
        }
    }
    return step;
}

struct State{
    int y,x,step;
    State(int _y,int _x,int _step){
        y = _y;
        x = _x;
        step = _step;
    }
    State(){

    }
};

bool vis[42][42];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int bfs(int inity, int initx){
    queue<State> que;
    que.push(State(inity, initx,1));
    memset(vis, false, sizeof(vis));
    while (!que.empty()) {
        State now = que.front();
        que.pop();
        int nowy = now.y;
        int nowx = now.x;
        if (vis[nowy][nowx]) {
            continue;
        }
        vis[nowy][nowx] = true;
        if (grid[nowy][nowx] == 'E') {
            return now.step;
        }
        for (int i = 0; i < 4; i++) {
            int nxty = nowy + dir[i][0];
            int nxtx = nowx + dir[i][1];
            if (grid[nxty][nxtx] && !vis[nxty][nxtx] && grid[nxty][nxtx] != '#') {
                que.push(State(nxty, nxtx,now.step+1));
            }
        }
    }
    return -1;
}


int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    while (caseCnt--) {
        int m,n;
        memset(grid, 0, sizeof(grid));
        scanf(" %d %d",&m,&n);
        int inity=0,initx=0,endy=0,endx=0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf(" %c",&grid[i][j]);
                if(grid[i][j] == 'S'){
                    inity = i;
                    initx = j;
                }
                if(grid[i][j] == 'E'){
                    endy = i;
                    endx = j;
                }
            }
        }
        swap(grid[inity][initx], grid[endy][endx]);
        printf("%d ",follow(endy, endx));
        swap(grid[inity][initx], grid[endy][endx]);
        printf("%d %d\n",follow(inity, initx),bfs(inity, initx));

    }


    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

char grid[42][42];

void counterClockwiseRotate(int &y,int &x){

int t = -y;

y = x;

x = t;

}

void clockwiseRotate(int &y,int &x){

int t = -x;

x = y;

y = t;

}

int follow(int inity,int initx){

int cury = inity,curx = initx,step = 1;

int diry = 0,dirx = -1;

while (grid[cury][curx] != 'E') {

for (int i = 0; i < 4; i++) {

int nxty = cury + diry;

int nxtx = curx + dirx;

if (grid[nxty][nxtx] && grid[nxty][nxtx] != '#') {

cury = nxty;

curx = nxtx;

step++;

counterClockwiseRotate(diry, dirx);

break;

}

clockwiseRotate(diry, dirx);

}

return step;

}

struct State{

int y,x,step;

State(int _y,int _x,int _step){

y = _y;

x = _x;

step = _step;

}

State(){

}

};

bool vis[42][42];

int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

int bfs(int inity, int initx){

queue<State> que;

que.push(State(inity, initx,1));

memset(vis, false, sizeof(vis));

while (!que.empty()) {

State now = que.front();

que.pop();

int nowy = now.y;

int nowx = now.x;

if (vis[nowy][nowx]) {

continue;

}

vis[nowy][nowx] = true;

if (grid[nowy][nowx] == 'E') {

return now.step;

}

for (int i = 0; i < 4; i++) {

int nxty = nowy + dir[i][0];

int nxtx = nowx + dir[i][1];

if (grid[nxty][nxtx] && !vis[nxty][nxtx] && grid[nxty][nxtx] != '#') {

que.push(State(nxty, nxtx,now.step+1));

}

return -1;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

while (caseCnt--) {

int m,n;

memset(grid, 0, sizeof(grid));

scanf(" %d %d",&m,&n);

int inity=0,initx=0,endy=0,endx=0;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

scanf(" %c",&grid[i][j]);

if(grid[i][j] == 'S'){

inity = i;

initx = j;

}

if(grid[i][j] == 'E'){

endy = i;

endx = j;

}

swap(grid[inity][initx], grid[endy][endx]);

printf("%d ",follow(endy, endx));

swap(grid[inity][initx], grid[endy][endx]);

printf("%d %d\n",follow(inity, initx),bfs(inity, initx));

}

return 0;

}

POJ 2386 Lake Counting / HDU 1241 Oil Deposits

September 10, 20152015-09-10hahaschool2 Comments

题意

在一片空地上，出现了若干水洼，对于一个有水的格子，他的八连通格子（上下左右左上左下右上右下）都可以看成和他连通形成一个大水洼。现在给你空地上水的配布，你要数出有多少个水洼。

思路

典型的“水洼问题”，利用DFS解决连通性问题是十分方便的。本题只要能够正确实现DFS就可以通过了，实现DFS的要点主要是正确地使用标记和正确的递归写法。对于DFS的实作原理不太理解的话请先思考树的先序遍历，可以参考我写的这篇文章。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

int N,M;
int dir[8][2] = {{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
char grid[102][102];

bool isValid(int y,int x){
    if (y < 1 || y > N) {
        return false;
    }
    if (x < 1 || x > M) {
        return false;
    }
    return grid[y][x] == 'W';
}

int vis[102][102];
bool dfs(int cury,int curx,int id){
    if (!vis[cury][curx] && isValid(cury, curx)) {
        vis[cury][curx] = id;
    }else{
        return false;
    }
    for (int i = 0; i < 8; i++) {
        int newy = cury + dir[i][0];
        int newx = curx + dir[i][1];
        if (isValid(newy, newx) && !vis[newy][newx]) {
            dfs(newy, newx, id);
        }
    }
    return true;
}

int main(){
    while (scanf(" %d %d",&N,&M) != EOF) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                scanf(" %c",&grid[i][j]);
            }
        }
        memset(vis, 0, sizeof(vis));
        int res = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (dfs(i, j, res)) {
                    res++;
                }
            }
        }
        cout << --res << endl;
    }


    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

int N,M;

int dir[8][2] = {{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};

char grid[102][102];

bool isValid(int y,int x){

if (y < 1 || y > N) {

return false;

}

if (x < 1 || x > M) {

return false;

}

return grid[y][x] == 'W';

}

int vis[102][102];

bool dfs(int cury,int curx,int id){

if (!vis[cury][curx] && isValid(cury, curx)) {

vis[cury][curx] = id;

}else{

return false;

}

for (int i = 0; i < 8; i++) {

int newy = cury + dir[i][0];

int newx = curx + dir[i][1];

if (isValid(newy, newx) && !vis[newy][newx]) {

dfs(newy, newx, id);

}

return true;

}

int main(){

while (scanf(" %d %d",&N,&M) != EOF) {

for (int i = 1; i <= N; i++) {

for (int j = 1; j <= M; j++) {

scanf(" %c",&grid[i][j]);

}

memset(vis, 0, sizeof(vis));

int res = 1;

for (int i = 1; i <= N; i++) {

for (int j = 1; j <= M; j++) {

if (dfs(i, j, res)) {

res++;

}

cout << --res << endl;

}

return 0;

}

POJ 2251 Dungeon Master

September 10, 20152015-09-10hahaschoolOne Comment

题意

给出一个三维迷宫，上下左右前后六联通的走法，给你起点和终点，要你求从起点到终点的最少步数。

思路

拿到问题，首先发现是在一个迷宫里面进行，联通方向有六个，求最短路，且数据规模较小，这些都是适用于BFS解题的特征。接下来的关键就是正确地实现BFS了，对BFS的实作原理不太理解的话，不妨先思考在一棵树上遍历时的BFS的实作过程。在BFS的实现过程中，需要正确地判断某个点是不是有效，需要在正确的时机打访问标记，需要正确地操作队列，注意这三点一般不会产生问题。本题并不需要我们实现图结构，因为迷宫本身就已经可以看成图了。在BFS过程中，因为搜索完当前深度的全部状态，才会取出更大深度的状态，所以在BFS过程中，只要我们进入了表示走到终点的状态，就无需再考虑其他状态了，因为即使其他状态也能表示到达终点，其深度（步数）也一定不会比第一个到达的状态少，这样可以节省一些时间。还有一些诸如“连通向量”等小技巧，可以减轻编码负担。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

char grid[32][32][32];//z,y,x
int L,R,C;//maxz maxy maxx
int dir[6][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};

struct Point {
    int z,y,x,step;
    Point(int _z,int _y,int _x,int _step){
        z = _z;
        y = _y;
        x = _x;
        step = _step;
    }
    Point(){

    }
};

bool isValid(int z,int y,int x){
    if (z < 1 || z > L) {
        return false;
    }
    if (y < 1 || y > R) {
        return false;
    }
    if (x < 1 || x > C) {
        return false;
    }
    if (grid[z][y][x] == '#') {
        return false;
    }
    return true;
}

bool vis[32][32][32];
int bfs(Point init){
    queue<Point> que;
    que.push(init);
    memset(vis, false, sizeof(vis));
    while (!que.empty()) {
        Point now = que.front();
        que.pop();
        if (vis[now.z][now.y][now.x]) {
            continue;
        }
        vis[now.z][now.y][now.x] = true;
        if (grid[now.z][now.y][now.x] == 'E') {
            return now.step;
        }
        for (int i = 0; i < 6; i++) {
            int newz = now.z + dir[i][0];
            int newy = now.y + dir[i][1];
            int newx = now.x + dir[i][2];
            if (!vis[newz][newy][newx] && isValid(newz, newy, newx)) {
                que.push(Point(newz,newy,newx,now.step+1));
            }
        }
    }
    return -1;
}

int main(){
    while (scanf(" %d %d %d",&L,&R,&C)) {
        if (L == 0 && R == 0 && C == 0) {
            break;
        }
        Point init;
        for (int i = 1; i <= L; i++) {
            for (int j = 1; j <= R; j++) {
                for (int k = 1; k <= C; k++) {
                    scanf(" %c",&grid[i][j][k]);
                    if (grid[i][j][k] == 'S') {
                        init = Point(i,j,k,0);
                    }
                }
            }
        }
        int res = bfs(init);
        if (res == -1) {
            cout << "Trapped!" << endl;
        }else{
            cout << "Escaped in " << res << " minute(s)." << endl;
        }

    }

    return 0;
}

100

101

102

103

104

105

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

char grid[32][32][32];//z,y,x

int L,R,C;//maxz maxy maxx

int dir[6][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};

struct Point {

int z,y,x,step;

Point(int _z,int _y,int _x,int _step){

z = _z;

y = _y;

x = _x;

step = _step;

}

Point(){

}

};

bool isValid(int z,int y,int x){

if (z < 1 || z > L) {

return false;

}

if (y < 1 || y > R) {

return false;

}

if (x < 1 || x > C) {

return false;

}

if (grid[z][y][x] == '#') {

return false;

}

return true;

}

bool vis[32][32][32];

int bfs(Point init){

queue<Point> que;

que.push(init);

memset(vis, false, sizeof(vis));

while (!que.empty()) {

Point now = que.front();

que.pop();

if (vis[now.z][now.y][now.x]) {

continue;

}

vis[now.z][now.y][now.x] = true;

if (grid[now.z][now.y][now.x] == 'E') {

return now.step;

}

for (int i = 0; i < 6; i++) {

int newz = now.z + dir[i][0];

int newy = now.y + dir[i][1];

int newx = now.x + dir[i][2];

if (!vis[newz][newy][newx] && isValid(newz, newy, newx)) {

que.push(Point(newz,newy,newx,now.step+1));

}

return -1;

}

int main(){

while (scanf(" %d %d %d",&L,&R,&C)) {

if (L == 0 && R == 0 && C == 0) {

break;

}

Point init;

for (int i = 1; i <= L; i++) {

for (int j = 1; j <= R; j++) {

for (int k = 1; k <= C; k++) {

scanf(" %c",&grid[i][j][k]);

if (grid[i][j][k] == 'S') {

init = Point(i,j,k,0);

}

int res = bfs(init);

if (res == -1) {

cout << "Trapped!" << endl;

}else{

cout << "Escaped in " << res << " minute(s)." << endl;

}

return 0;

}

POJ 1469 COURSES

August 29, 20152015-08-29hahaschoolLeave a comment

题意

判定给出的二分图是否存在完备匹配。

思路

按照题目要求直接建立二分路，之后运行最大匹配算法，出答案。

代码

使用了匈牙利算法。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;


#pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H)

const int MAXN = 305;
const int INF = 0x3f3f3f3f;

struct Node{
    vector<int> to;
} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny
int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]
bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){
    for (int i = 0; i < MAXN; i++) {
        X[i].to.clear();
        Y[i].to.clear();
    }
    memset(matchX, -1, sizeof(matchX));
    memset(matchY, -1, sizeof(matchY));
}

int ap_dfs(int u){
    for (int i = 0; i < X[u].to.size(); i++) {
        int v = X[u].to[i];
        if (!ap_vis[v]) {
            ap_vis[v] = true;
            if (matchY[v] == -1 || ap_dfs(matchY[v])) {
                matchX[u] = v;
                matchY[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int BGM_H(){
    int ret = 0;
    memset(matchX, -1, sizeof(matchX));
    memset(matchY, -1, sizeof(matchY));
    for (int i = 1; i <= nx; i++) {
        if (matchX[i] == -1) {
            memset(ap_vis, false, sizeof(ap_vis));
            ret += ap_dfs(i);
        }
    }
    return ret;
}

#pragma mark -

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for (int d = 1; d <= caseCnt; d++) {
        int p,n;
        scanf(" %d %d",&p,&n);
        init();
        nx = p;
        ny = n;
        for (int i = 1; i <= p; i++) {
            int cnt;
            scanf(" %d",&cnt);
            for (int j = 1; j <= cnt; j++) {
                int tmp;
                scanf(" %d",&tmp);
                X[i].to.push_back(tmp);
            }
        }
        int res = BGM_H();
        //cerr << res << endl;
        if (res == p) {
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H)

const int MAXN = 305;

const int INF = 0x3f3f3f3f;

struct Node{

vector<int> to;

} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny

int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]

bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){

for (int i = 0; i < MAXN; i++) {

X[i].to.clear();

Y[i].to.clear();

}

memset(matchX, -1, sizeof(matchX));

memset(matchY, -1, sizeof(matchY));

}

int ap_dfs(int u){

for (int i = 0; i < X[u].to.size(); i++) {

int v = X[u].to[i];

if (!ap_vis[v]) {

ap_vis[v] = true;

if (matchY[v] == -1 || ap_dfs(matchY[v])) {

matchX[u] = v;

matchY[v] = u;

return 1;

}

return 0;

}

int BGM_H(){

int ret = 0;

memset(matchX, -1, sizeof(matchX));

memset(matchY, -1, sizeof(matchY));

for (int i = 1; i <= nx; i++) {

if (matchX[i] == -1) {

memset(ap_vis, false, sizeof(ap_vis));

ret += ap_dfs(i);

}

return ret;

}

#pragma mark -

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for (int d = 1; d <= caseCnt; d++) {

int p,n;

scanf(" %d %d",&p,&n);

init();

nx = p;

ny = n;

for (int i = 1; i <= p; i++) {

int cnt;

scanf(" %d",&cnt);

for (int j = 1; j <= cnt; j++) {

int tmp;

scanf(" %d",&tmp);

X[i].to.push_back(tmp);

}

int res = BGM_H();

//cerr << res << endl;

if (res == p) {

cout << "YES" << endl;

}else{

cout << "NO" << endl;

}

POJ 1325 Machine Schedule

August 29, 20152015-08-29hahaschoolOne Comment

题意

给你两台机器和k个工件，要你设计最优调度方案。对于每个机器，一共有0 ~ n-1(或者是m-1)这n(或者是m)个状态，初始状态都是0。对于每个工件，要么在x号状态下加工，要么在y号状态下加工。你要给出两台机器一共最少要切换多少次状态，才可以加工完全部工件。

思路

这个题对于建图是很讲究的，第一眼看上去很有二分图的意思。但是如果你这么建图：一边是0~max(m,n)这些状态(因为无论是两台还是一台，其实都是一样的，因为机器运转的时间是无限的，理论上讲就算只给一个机器，也能完成任务，而且和两台机器所需要的切换次数一样)，另一边是0~k这些工件，每一个工件都和他可以被加工的状态连上一条边。

但是这么建图并不能解决问题，首先，只要工件可以在0状态加工，就可以看成不存在了，因为机器无需切换状态就可以加工好，这样，我们在图中所有与0状态相连的点，和0状态本身都要去掉。其次，现在我们规约好的问题已经变成了：在一边的图中选出尽可能少的点，使得这些点的所连接的点可以覆盖对面全部的点。这是典型的“最小支配集”问题。最小支配集问题目前还是NP困难问题。所以此路已经不通了。

我们只好换一种思路，我们发现，如果把一个工件可以加工的两个状态连接起来，建立二分图之后。在这个图上，图的两边分别是A机器和B机器，图上的每一条边代表一个工件，我们要求的东西就变成了选出最少的点，使得所引出的边的集合中包含了全部的边，也就是“最小点覆盖问题”。二分图的最大匹配数等于最小覆盖数。问题可做了。

代码

使用了匈牙利算法。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;


int n,m,k;

#pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H)

const int MAXN = 1050;

struct Node{
    vector<int> to;
} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny
int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]
bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){
    for (int i = 0; i < MAXN; i++) {
        X[i].to.clear();
        Y[i].to.clear();
    }
    memset(matchX, -1, sizeof(matchX));
    memset(matchY, -1, sizeof(matchY));
}

int ap_dfs(int u){
    for (int i = 0; i < X[u].to.size(); i++) {
        int v = X[u].to[i];
        if (!ap_vis[v]) {
            ap_vis[v] = true;
            if (matchY[v] == -1 || ap_dfs(matchY[v])) {
                matchX[u] = v;
                matchY[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int BGM_H(){
    int ret = 0;
    memset(matchX, -1, sizeof(matchX));
    memset(matchY, -1, sizeof(matchY));
    for (int i = 1; i < nx; i++) {
        if (matchX[i] == -1) {
            memset(ap_vis, false, sizeof(ap_vis));
            if (ap_dfs(i)) {
                ret++;
            }
        }
    }
    return ret;
}

#pragma mark -

bool vis[105][105];

int main(){
    while (scanf(" %d",&n) != EOF) {
        if (!n) {
            break;
        }
        memset(vis, 0, sizeof(vis));
        scanf(" %d %d",&m,&k);
        nx = n;
        ny = k;
        init();
        for (int i = 1; i <= k; i++) {
            int cur,x,y;
            scanf(" %d %d %d",&cur,&x,&y);
            if (x*y != 0 && !vis[x][y]) {
                X[x].to.push_back(y);
                vis[x][y] = true;
            }
        }
        cout << BGM_H() << endl;//must not use cerr for output
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

int n,m,k;

#pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H)

const int MAXN = 1050;

struct Node{

vector<int> to;

} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny

int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]

bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){

for (int i = 0; i < MAXN; i++) {

X[i].to.clear();

Y[i].to.clear();

}

memset(matchX, -1, sizeof(matchX));

memset(matchY, -1, sizeof(matchY));

}

int ap_dfs(int u){

for (int i = 0; i < X[u].to.size(); i++) {

int v = X[u].to[i];

if (!ap_vis[v]) {

ap_vis[v] = true;

if (matchY[v] == -1 || ap_dfs(matchY[v])) {

matchX[u] = v;

matchY[v] = u;

return 1;

}

return 0;

}

int BGM_H(){

int ret = 0;

memset(matchX, -1, sizeof(matchX));

memset(matchY, -1, sizeof(matchY));

for (int i = 1; i < nx; i++) {

if (matchX[i] == -1) {

memset(ap_vis, false, sizeof(ap_vis));

if (ap_dfs(i)) {

ret++;

}

return ret;

}

#pragma mark -

bool vis[105][105];

int main(){

while (scanf(" %d",&n) != EOF) {

if (!n) {

break;

}

memset(vis, 0, sizeof(vis));

scanf(" %d %d",&m,&k);

nx = n;

ny = k;

init();

for (int i = 1; i <= k; i++) {

int cur,x,y;

scanf(" %d %d %d",&cur,&x,&y);

if (x*y != 0 && !vis[x][y]) {

X[x].to.push_back(y);

vis[x][y] = true;

}

cout << BGM_H() << endl;//must not use cerr for output

}

return 0;

}

POJ 2594 Treasure Exploration

August 29, 20152015-08-29hahaschoolLeave a comment

题意

给出一个DAG（有向，没有环的图），现在要你选出尽可能少的几条路径，使得只要把你选出来的路径都走了一遍，就可以保证你已经走过的图中的每一个节点。注意，路径与路径之间，可以有公共点（即允许路径相交）。

思路

典型的“最小路径覆盖”问题。在这里直接给出此类问题的解法：

有向无环图最小不相交路径覆盖

定义：用最少的不相交路径覆盖所有顶点。

定理：把原图中的每个点V拆成Vx和Vy，如果有一条有向边A->B，那么就加边Ax-By。这样就得到了一个二分图，最小路径覆盖=原图的节点数-新图最大匹配。

简单证明：一开始每个点都独立的为一条路径，总共有n条不相交路径。我们每次在二分图里加一条边就相当于把两条路径合成了一条路径，因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。所以有：最小路径覆盖=原图的节点数-新图最大匹配。

有向无环图最小可相交路径覆盖

定义：用最小的可相交路径覆盖所有顶点。

算法：先用floyd求出原图的传递闭包，即如果a到b有路，那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。

所谓传递闭包(Transitive Closure)就是指把原图里面所有能直接间接联通的点之间都给连上边（如果有联通的方向限制，这个方向也要保留）之后形成的图，也就是说只要在传递闭包中存在A->B，就一定可以在原图中找到一条从A到B的路径。求传递闭包使用Warshall算法，最简单的实现就是借助邻接矩阵了（下图直接截自离散数学课件）：

代码

以下实现使用了Hopcraft-Karp算法和Warshall算法。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;


#pragma mark - Hopcroft-Karp Algorithm for BiGraph Matching (BGM_HK)

const int MAXN = 1050;
const int INF = 0x3f3f3f3f;

struct Node{
    vector<int> to;
} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny
int dis;

int first[MAXN];
int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]
int disX[MAXN],disY[MAXN];
bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){
    for (int i = 0; i < MAXN; i++) {
        X[i].to.clear();
        Y[i].to.clear();
    }
    memset(first, -1, sizeof(first));
    memset(matchX, -1, sizeof(matchX));
    memset(matchY, -1, sizeof(matchY));
}

bool hk_bfs(){
    queue<int> que;
    dis = INF;//records currently the smallest distance(length of the augmented path)
    memset(disX, -1, sizeof(disX));//reset disX and disY array to the status indicating that no match was made
    memset(disY, -1, sizeof(disY));
    for (int i = 1; i <= nx; i++) {
        //iterate the LHS and find any available not-matched nodes
        if (matchX[i] == -1) {
            //if this node is not matched,add this node into the queue
            que.push(i);
            //the distance(length of the augmented path) should be zero for a bold, unmatched point
            disX[i] = 0;
        }
    }
    while (!que.empty()) {
        int u = que.front();//"current node"
        que.pop();
        if (disX[u] > dis) {
            //if the augmented path derived from u is larger than someone we had examined,we don't need to examine this point anymore
            break;
        }
        for (int i = 0; i < X[u].to.size(); i++) {
            //iterate the nodes connected with current node (all connected nodes are,certainally, belongs to RHS)
            int v = X[u].to[i];
            if (disY[v] == -1) {
                //if the distance data is void for the connected RHS node,we should update it
                disY[v] = disX[u] + 1;
                if (matchY[v] == -1) {
                    //in this case, we can terminate the current augment path here
                    dis = disY[v];
                }else {
                    //in this case,we try to go deeper on the existed augment path
                    disX[matchY[v]] = disY[v] + 1;
                    que.push(matchY[v]);
                }
            }
        }
    }
    return dis != INF;//if dis == INF, this means no longer augment path can be made
}

int ap_dfs(int u){
    //the current LHS node is u
    for (int i = 0; i < X[u].to.size(); i++) {
        //iterate the connected RHS node v
        int v = X[u].to[i];
        if (!ap_vis[v] && disY[v] == disX[u] + 1) {
            //we want to find a non-visited RHS node with the desired distance
            ap_vis[v] = true;//mark visited
            if (matchY[v] != -1 && disY[v] == dis) {
                //if this node has already matched and the distance is what we desired --> appropriate augment path exist, no need to advance
                continue;
            }
            if (matchY[v] == -1 || ap_dfs(matchY[v])) {
                //hangary algo.
                //if matchY = -1 --> augment path terminated，else go deeper
                matchX[u] = v;
                matchY[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int BGM_HK(){
    int ans = 0;
    while (hk_bfs()) {
        memset(ap_vis, false, sizeof(ap_vis));
        for (int i = 1; i <= nx; i++) {
            if (matchX[i] == -1) {
                ans += ap_dfs(i);
            }
        }
    }
    return ans;
}

#pragma mark - Warshall Algorithm for Transitive Closure (TC_W)
int conmat[MAXN][MAXN];
int trans[2][MAXN][MAXN];

//index begins from 1
//should adopt trans[n%2] as transitive closure

void TC_W(int n){
    memcpy(trans[0], conmat, sizeof(conmat));
    memcpy(trans[1], conmat, sizeof(conmat));
    for (int d = 1; d <= n; d++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                trans[d%2][i][j] = trans[(d-1)%2][i][j] | (trans[(d-1)%2][i][d] & trans[(d-1)%2][d][j]);
            }
        }
    }
}

#pragma mark -

int main(){
    int n,m;
    while (scanf(" %d %d",&n,&m) != EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        memset(conmat, 0, sizeof(conmat));
        for (int i = 1; i <= m; i++) {
            int from,to;
            scanf(" %d %d",&from,&to);
            conmat[from][to] = 1;
        }
        TC_W(n);
        init();
        nx = ny = n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    continue;
                }
                if (trans[n%2][i][j]) {
                    X[i].to.push_back(j);
                }
            }
        }
        int res = BGM_HK();
        cout << nx - res << endl;
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#pragma mark - Hopcroft-Karp Algorithm for BiGraph Matching (BGM_HK)

const int MAXN = 1050;

const int INF = 0x3f3f3f3f;

struct Node{

vector<int> to;

} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny

int dis;

int first[MAXN];

int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]

int disX[MAXN],disY[MAXN];

bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){

for (int i = 0; i < MAXN; i++) {

X[i].to.clear();

Y[i].to.clear();

}

memset(first, -1, sizeof(first));

memset(matchX, -1, sizeof(matchX));

memset(matchY, -1, sizeof(matchY));

}

bool hk_bfs(){

queue<int> que;

dis = INF;//records currently the smallest distance(length of the augmented path)

memset(disX, -1, sizeof(disX));//reset disX and disY array to the status indicating that no match was made

memset(disY, -1, sizeof(disY));

for (int i = 1; i <= nx; i++) {

//iterate the LHS and find any available not-matched nodes

if (matchX[i] == -1) {

//if this node is not matched,add this node into the queue

que.push(i);

//the distance(length of the augmented path) should be zero for a bold, unmatched point

disX[i] = 0;

}

while (!que.empty()) {

int u = que.front();//"current node"

que.pop();

if (disX[u] > dis) {

//if the augmented path derived from u is larger than someone we had examined,we don't need to examine this point anymore

break;

}

for (int i = 0; i < X[u].to.size(); i++) {

//iterate the nodes connected with current node (all connected nodes are,certainally, belongs to RHS)

int v = X[u].to[i];

if (disY[v] == -1) {

//if the distance data is void for the connected RHS node,we should update it

disY[v] = disX[u] + 1;

if (matchY[v] == -1) {

//in this case, we can terminate the current augment path here

dis = disY[v];

}else {

//in this case,we try to go deeper on the existed augment path

disX[matchY[v]] = disY[v] + 1;

que.push(matchY[v]);

}

return dis != INF;//if dis == INF, this means no longer augment path can be made

}

int ap_dfs(int u){

//the current LHS node is u

for (int i = 0; i < X[u].to.size(); i++) {

//iterate the connected RHS node v

int v = X[u].to[i];

if (!ap_vis[v] && disY[v] == disX[u] + 1) {

//we want to find a non-visited RHS node with the desired distance

ap_vis[v] = true;//mark visited

if (matchY[v] != -1 && disY[v] == dis) {

//if this node has already matched and the distance is what we desired --> appropriate augment path exist, no need to advance

continue;

}

if (matchY[v] == -1 || ap_dfs(matchY[v])) {

//hangary algo.

//if matchY = -1 --> augment path terminated，else go deeper

matchX[u] = v;

matchY[v] = u;

return 1;

}

return 0;

}

int BGM_HK(){

int ans = 0;

while (hk_bfs()) {

memset(ap_vis, false, sizeof(ap_vis));

for (int i = 1; i <= nx; i++) {

if (matchX[i] == -1) {

ans += ap_dfs(i);

}

return ans;

}

#pragma mark - Warshall Algorithm for Transitive Closure (TC_W)

int conmat[MAXN][MAXN];

int trans[2][MAXN][MAXN];

//index begins from 1

//should adopt trans[n%2] as transitive closure

void TC_W(int n){

memcpy(trans[0], conmat, sizeof(conmat));

memcpy(trans[1], conmat, sizeof(conmat));

for (int d = 1; d <= n; d++) {

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

trans[d%2][i][j] = trans[(d-1)%2][i][j] | (trans[(d-1)%2][i][d] & trans[(d-1)%2][d][j]);

}

#pragma mark -

int main(){

int n,m;

while (scanf(" %d %d",&n,&m) != EOF) {

if (n == 0 && m == 0) {

break;

}

memset(conmat, 0, sizeof(conmat));

for (int i = 1; i <= m; i++) {

int from,to;

scanf(" %d %d",&from,&to);

conmat[from][to] = 1;

}

TC_W(n);

init();

nx = ny = n;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= n; j++) {

if (i == j) {

continue;

}

if (trans[n%2][i][j]) {

X[i].to.push_back(j);

}

int res = BGM_HK();

cout << nx - res << endl;

}

POJ 2446 Chessboard

August 29, 20152015-08-29hahaschoolLeave a comment

题意

给出一个M＊N大小的棋盘(M,N都非常小)，棋盘上戳了几个洞，然后问你有没有可能用若干张1*2的骨牌，横着或者竖着填满整个棋盘，有洞的地方是不可以放置骨牌的。

思路

因为骨牌是1*2的，如果我们把整个棋盘看成一个图，每个没洞的地方都是一个节点，在棋盘上只要相邻（上下左右四联通）就可以看成两个节点有一条边相连，这样我们就可以发现，每一块骨牌正好就是图上的一条边。所以我们就把问题转化为了：给出一个图，要你用选出尽可能少的边，使得图上的每一个顶点都是选出的边中的某一条的端末，也就是“最小边覆盖”问题。

最小边覆盖=图中点的个数-最大匹配数=最大独立集

所以接下来的事情就很简单，按着上面的说法建图，然后运行一次最大匹配算法，之后作个差就搞定了。

还要注意一点，本题数据给出的形式可能和预想的不一样，挖洞的点是横坐标在前，纵坐标在后，如果WA，不妨检查一下是不是输入的时候做反了。

代码

本实现使用了匈牙利算法。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

#pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H)

const int MAXN = 1050;
const int INF = 0x3f3f3f3f;

struct Node{
    vector<int> to;
} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny
int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]
bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){
    for (int i = 0; i < MAXN; i++) {
        X[i].to.clear();
        Y[i].to.clear();
    }
    memset(matchX, -1, sizeof(matchX));
    memset(matchY, -1, sizeof(matchY));
}

int ap_dfs(int u){
    for (int i = 0; i < X[u].to.size(); i++) {
        int v = X[u].to[i];
        if (!ap_vis[v]) {
            ap_vis[v] = true;
            if (matchY[v] == -1 || ap_dfs(matchY[v])) {
                matchX[u] = v;
                matchY[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int BGM_H(){
    int ret = 0;
    memset(matchX, -1, sizeof(matchX));
    memset(matchY, -1, sizeof(matchY));
    for (int i = 0; i < nx; i++) {
        if (matchX[i] == -1) {
            memset(ap_vis, false, sizeof(ap_vis));
            ret += ap_dfs(i);
        }
    }
    return ret;
}

#pragma mark -

bool board[40][40];
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

inline int id(int y,int x,int m){
    return (y-1)*m+x-1;
}

int main(){
    int n,m,k;
    while (scanf(" %d %d %d",&n,&m,&k) != EOF) {
        memset(board, false, sizeof(false));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                board[i][j] = true;
            }
        }
        for (int i = 1; i <= k; i++) {
            int y,x;
            scanf(" %d %d",&x,&y);
            board[y][x] = false;
        }
        init();
        int availPt = n*m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (!board[i][j]) {
                    availPt--;
                    continue;
                }
                for (int d = 0; d < 4; d++) {
                    int ny = i + dir[d][0];
                    int nx = j + dir[d][1];
                    if (board[ny][nx]) {
                        X[id(i,j,m)].to.push_back(id(ny, nx, m));
                        Y[id(ny, nx, m)].to.push_back(id(i, j, m));
                    }
                }
            }
        }
        nx = ny = n*m;
        int res = BGM_H();
        //cout << res << endl;
        if (res == availPt) {
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H)

const int MAXN = 1050;

const int INF = 0x3f3f3f3f;

struct Node{

vector<int> to;

} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny

int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]

bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){

for (int i = 0; i < MAXN; i++) {

X[i].to.clear();

Y[i].to.clear();

}

memset(matchX, -1, sizeof(matchX));

memset(matchY, -1, sizeof(matchY));

}

int ap_dfs(int u){

for (int i = 0; i < X[u].to.size(); i++) {

int v = X[u].to[i];

if (!ap_vis[v]) {

ap_vis[v] = true;

if (matchY[v] == -1 || ap_dfs(matchY[v])) {

matchX[u] = v;

matchY[v] = u;

return 1;

}

return 0;

}

int BGM_H(){

int ret = 0;

memset(matchX, -1, sizeof(matchX));

memset(matchY, -1, sizeof(matchY));

for (int i = 0; i < nx; i++) {

if (matchX[i] == -1) {

memset(ap_vis, false, sizeof(ap_vis));

ret += ap_dfs(i);

}

return ret;

}

#pragma mark -

bool board[40][40];

int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

inline int id(int y,int x,int m){

return (y-1)*m+x-1;

}

int main(){

int n,m,k;

while (scanf(" %d %d %d",&n,&m,&k) != EOF) {

memset(board, false, sizeof(false));

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

board[i][j] = true;

}

for (int i = 1; i <= k; i++) {

int y,x;

scanf(" %d %d",&x,&y);

board[y][x] = false;

}

init();

int availPt = n*m;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

if (!board[i][j]) {

availPt--;

continue;

}

for (int d = 0; d < 4; d++) {

int ny = i + dir[d][0];

int nx = j + dir[d][1];

if (board[ny][nx]) {

X[id(i,j,m)].to.push_back(id(ny, nx, m));

Y[id(ny, nx, m)].to.push_back(id(i, j, m));

}

nx = ny = n*m;

int res = BGM_H();

//cout << res << endl;

if (res == availPt) {

cout << "YES" << endl;

}else{

cout << "NO" << endl;

}

POJ 1274 The Perfect Stall

August 27, 20152015-08-27hahaschoolOne Comment

题意

求二分图最大匹配。

思路

教学题，只要使用了二分图／网络流就可以通过。在这里我强行使用了Hopcroft-Karp Algorithm，因为看了很长时间自己也很难理解，决定抄一遍别人的代码仔细领悟。核心部分我加了好多注释帮助理解。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

#pragma mark - Hopcroft-Karp Algorithm for BiGraph Matching (BGM_HK)

const int MAXN = 210;
const int INF = 0x3f3f3f3f;

struct Node{
    vector<int> to;
} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny
int dis;

int first[MAXN];
int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]
int disX[MAXN],disY[MAXN];
bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){
    memset(first, -1, sizeof(first));
    memset(matchX, -1, sizeof(matchX));
    memset(matchY, -1, sizeof(matchY));
}

bool bfs(){
    queue<int> que;
    dis = INF;//records currently the smallest distance(length of the augmented path)
    memset(disX, -1, sizeof(disX));//reset disX and disY array to the status indicating that no match was made
    memset(disY, -1, sizeof(disY));
    for (int i = 0; i < nx; i++) {
        //iterate the LHS and find any available not-matched nodes
        if (matchX[i] == -1) {
            //if this node is not matched,add this node into the queue
            que.push(i);
            //the distance(length of the augmented path) should be zero for a bold, unmatched point
            disX[i] = 0;
        }
    }
    while (!que.empty()) {
        int u = que.front();//"current node"
        que.pop();
        if (disX[u] > dis) {
            //if the augmented path derived from u is larger than someone we had examined,we don't need to examine this point anymore
            break;
        }
        for (int i = 0; i < X[u].to.size(); i++) {
            //iterate the nodes connected with current node (all connected nodes are,certainally, belongs to RHS)
            int v = X[u].to[i];
            if (disY[v] == -1) {
                //if the distance data is void for the connected RHS node,we should update it
                disY[v] = disX[u] + 1;
                if (matchY[v] == -1) {
                    //in this case, we can terminate the current augment path here
                    dis = disY[v];
                }else {
                    //in this case,we try to go deeper on the existed augment path
                    disX[matchY[v]] = disY[v] + 1;
                    que.push(matchY[v]);
                }
            }
        }
    }
    return dis != INF;//if dis == INF, this means no longer augment path can be made
}

int dfs(int u){
    //the current LHS node is u
    for (int i = 0; i < X[u].to.size(); i++) {
        //iterate the connected RHS node v
        int v = X[u].to[i];
        if (!ap_vis[v] && disY[v] == disX[u] + 1) {
            //we want to find a non-visited RHS node with the desired distance
            ap_vis[v] = true;//mark visited
            if (matchY[v] != -1 && disY[v] == dis) {
                //if this node has already matched and the distance is what we desired --> appropriate augment path exist, no need to advance
                continue;
            }
            if (matchY[v] == -1 || dfs(matchY[v])) {
                //hangary algo.
                //if matchY = -1 --> augment path terminated，else go deeper
                matchX[u] = v;
                matchY[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int BGM_HK(){
    int ans = 0;
    while (bfs()) {
        memset(ap_vis, false, sizeof(ap_vis));
        for (int i = 0; i < nx; i++) {
            if (matchX[i] == -1) {
                ans += dfs(i);
            }
        }
    }
    return ans;
}

#pragma mark -

int main(){
    int n,m;
    while (scanf(" %d %d",&n,&m) != EOF) {
        nx = n,ny = m;
        init();
        for (int i = 0; i < n; i++) {
            X[i].to.clear();
        }
        for (int i = 0; i < m; i++) {
            Y[i].to.clear();
        }
        for (int i = 0; i < n; i++) {
            int q;
            scanf(" %d",&q);
            for (int j = 1; j <= q; j++) {
                int tmp;
                scanf(" %d",&tmp);
                tmp--;
                X[i].to.push_back(tmp);
                Y[tmp].to.push_back(i);
            }
        }
        cout << BGM_HK() << endl;
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#pragma mark - Hopcroft-Karp Algorithm for BiGraph Matching (BGM_HK)

const int MAXN = 210;

const int INF = 0x3f3f3f3f;

struct Node{

vector<int> to;

} X[MAXN],Y[MAXN];//index starts from 0

int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny

int dis;

int first[MAXN];

int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y]

int disX[MAXN],disY[MAXN];

bool ap_vis[MAXN];//vis marking array for augment path searching

void init(){

memset(first, -1, sizeof(first));

memset(matchX, -1, sizeof(matchX));

memset(matchY, -1, sizeof(matchY));

}

bool bfs(){

queue<int> que;

dis = INF;//records currently the smallest distance(length of the augmented path)

memset(disX, -1, sizeof(disX));//reset disX and disY array to the status indicating that no match was made

memset(disY, -1, sizeof(disY));

for (int i = 0; i < nx; i++) {

//iterate the LHS and find any available not-matched nodes

if (matchX[i] == -1) {

//if this node is not matched,add this node into the queue

que.push(i);

//the distance(length of the augmented path) should be zero for a bold, unmatched point

disX[i] = 0;

}

while (!que.empty()) {

int u = que.front();//"current node"

que.pop();

if (disX[u] > dis) {

//if the augmented path derived from u is larger than someone we had examined,we don't need to examine this point anymore

break;

}

for (int i = 0; i < X[u].to.size(); i++) {

//iterate the nodes connected with current node (all connected nodes are,certainally, belongs to RHS)

int v = X[u].to[i];

if (disY[v] == -1) {

//if the distance data is void for the connected RHS node,we should update it

disY[v] = disX[u] + 1;

if (matchY[v] == -1) {

//in this case, we can terminate the current augment path here

dis = disY[v];

}else {

//in this case,we try to go deeper on the existed augment path

disX[matchY[v]] = disY[v] + 1;

que.push(matchY[v]);

}

return dis != INF;//if dis == INF, this means no longer augment path can be made

}

int dfs(int u){

//the current LHS node is u

for (int i = 0; i < X[u].to.size(); i++) {

//iterate the connected RHS node v

int v = X[u].to[i];

if (!ap_vis[v] && disY[v] == disX[u] + 1) {

//we want to find a non-visited RHS node with the desired distance

ap_vis[v] = true;//mark visited

if (matchY[v] != -1 && disY[v] == dis) {

//if this node has already matched and the distance is what we desired --> appropriate augment path exist, no need to advance

continue;

}

if (matchY[v] == -1 || dfs(matchY[v])) {

//hangary algo.

//if matchY = -1 --> augment path terminated，else go deeper

matchX[u] = v;

matchY[v] = u;

return 1;

}

return 0;

}

int BGM_HK(){

int ans = 0;

while (bfs()) {

memset(ap_vis, false, sizeof(ap_vis));

for (int i = 0; i < nx; i++) {

if (matchX[i] == -1) {

ans += dfs(i);

}

return ans;

}

#pragma mark -

int main(){

int n,m;

while (scanf(" %d %d",&n,&m) != EOF) {

nx = n,ny = m;

init();

for (int i = 0; i < n; i++) {

X[i].to.clear();

}

for (int i = 0; i < m; i++) {

Y[i].to.clear();

}

for (int i = 0; i < n; i++) {

int q;

scanf(" %d",&q);

for (int j = 1; j <= q; j++) {

int tmp;

scanf(" %d",&tmp);

tmp--;

X[i].to.push_back(tmp);

Y[tmp].to.push_back(i);

}

cout << BGM_HK() << endl;

}

POJ 3090 Visible Lattice Points

August 22, 20152015-08-22hahaschoolLeave a comment

题意

给出了一个1001×1001的点阵，和查询q，你要求出从(0,0)点到(q,q)点有多少种不同的点到原点的斜率（也就是题目中所说的“可见”），原点到原点不算。

思路

很直接的就可以想到算出所有的点到原点的斜率，预处理出答案，我们的做法是：从原点开始，一圈一圈地向外扩张，对于每个点都计算一边斜率，然后确认该斜率是否出现过，没出现过的话，当前圈上的点到原点的不同的斜率个数+1，这样求出每一圈的数目，最后我们再求一个前缀和就好了。

时间很理想，是O(n^2*log(n))的，然而POJ上超时了。我拿到ideone上测速，是700ms，可以过的，可能是评测机不在状态吧ˊ_>ˋ。补救的方法就是打了个表，反正数据也很少。

然而这个题的精髓并不是这么水过去的，这个题其实是一个包装过了的法雷级数(Wikipedia::法里数列可能需要科学上网)，如果试着一圈圈地写一下斜率，就会发现每一圈正好满足分子和分母互质的特性，每一圈的个数其实是欧拉函数值，整个答案是欧拉函数前缀和。所以我们就有了O(n)，的处理方法，详细的可以看这个题POJ 2478 Farey Sequence。

明明是刚做过的题居然都没有反应过来看来我真的是太迟钝了呢。

代码(暴力解法)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct Fac{
    int up;
    int down;
    int gcd(int a,int b){
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
    void reduce(){
        int _gcd = gcd(up, down);
        up /= _gcd;
        down /= _gcd;
    }
    friend bool operator < (Fac a,Fac b){
        if(a.up == b.up){
            return a.down < b.down;
        }else
            return a.up < b.up;
    }
};

Fac tg(int x,int y){
    Fac ret;
    ret.up = y;
    ret.down = x;
    ret.reduce();
    return ret;
}

set<Fac> vis;
int ans[1001];

void get_ans(){
    for (int i = 1; i <= 1000; i++) {
        int x = 0, y = i;
        for (x = 0; x <= i; x++) {
            Fac _tg = tg(x, y);
            if (!vis.count(_tg)) {
                vis.insert(_tg);
                ans[i]++;
            }
        }
        x = i;
        for (y = i-1; y >= 0; y--) {
            Fac _tg = tg(x, y);
            if (!vis.count(_tg)) {
                vis.insert(_tg);
                ans[i]++;
            }
        }
        ans[i] += ans[i-1];
    }
}

int main(){
    get_ans();
    int caseCnt;
    scanf(" %d",&caseCnt);
    for (int d = 1; d <= caseCnt; d++) {
        int q;
        scanf(" %d",&q);
        printf("%d %d %d\n",d,q,ans[q]);
    }
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct Fac{

int up;

int down;

int gcd(int a,int b){

if (b == 0) {

return a;

}

return gcd(b, a%b);

}

void reduce(){

int _gcd = gcd(up, down);

up /= _gcd;

down /= _gcd;

}

friend bool operator < (Fac a,Fac b){

if(a.up == b.up){

return a.down < b.down;

}else

return a.up < b.up;

}

};

Fac tg(int x,int y){

Fac ret;

ret.up = y;

ret.down = x;

ret.reduce();

return ret;

}

set<Fac> vis;

int ans[1001];

void get_ans(){

for (int i = 1; i <= 1000; i++) {

int x = 0, y = i;

for (x = 0; x <= i; x++) {

Fac _tg = tg(x, y);

if (!vis.count(_tg)) {

vis.insert(_tg);

ans[i]++;

}

x = i;

for (y = i-1; y >= 0; y--) {

Fac _tg = tg(x, y);

if (!vis.count(_tg)) {

vis.insert(_tg);

ans[i]++;

}

ans[i] += ans[i-1];

}

int main(){

get_ans();

int caseCnt;

scanf(" %d",&caseCnt);

for (int d = 1; d <= caseCnt; d++) {

int q;

scanf(" %d",&q);

printf("%d %d %d\n",d,q,ans[q]);

}

POJ 2478 Farey Sequence

August 21, 20152015-08-21hahaschoolOne Comment

题意

介绍性的问题，法雷级数(Wikipedia::法里數列可能需要科学上网)。

简单暴力，给出一个n，求出对于1～n中每一个数，有多少个小于等于他的数与他互质，把这些数量加在一起是多少，其实就是求欧拉函数的前缀和。

思路

欧拉函数有两种得到的方法，一是使用分解因子的方法，得到单个数的欧拉函数值，时间复杂度O(sqrt(n) * log(n))。如下：

//only for single number circumstances
long long s_phi(long long n)
{
    long long m=(long long)sqrt(n+0.5),ans=n;
    for(long long i=2;i<=m;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

//only for single number circumstances

long long s_phi(long long n)

{

long long m=(long long)sqrt(n+0.5),ans=n;

for(long long i=2;i<=m;i++)

{

if(n%i==0)

{

ans=ans/i*(i-1);

while(n%i==0)n/=i;

}

if(n>1)ans=ans/n*(n-1);

return ans;

}

可以发现这样算的话如果只求一个数的欧拉函数还是不亏的，但是如果要求非常非常多的欧拉函数，时间就会爆炸，所以我们不可以在这个题用这种方法。

第二种方法是利用欧拉函数的若干性质：欧拉函数线性筛法详解(Lytning)，然后把素数的线性筛法和求欧拉函数结合到一起，如果要求非常多的欧拉函数，使用这种方法预处理是非常快的，而且还顺便求了素数，一石二鸟。

const int N = 1000000;
int n;
int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合
bool mark[N+10];
void getphi()
{
    int i,j;
    phi[1]=1;
    for(i=2;i<=N;i++)//相当于分解质因式的逆过程
    {
        if(!mark[i])
        {
            prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
            phi[i]=i-1;//当 i 是素数时 phi[i]=i-1
        }
        for(j=1;j<=tot;j++)
        {
            if(i*prime[j]>N)  break;
            mark[i*prime[j]]=1;//确定i*prime[j]不是素数
            if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数
            {
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
        }
    }
}

const int N = 1000000;

int n;

int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合

bool mark[N+10];

void getphi()

{

int i,j;

phi[1]=1;

for(i=2;i<=N;i++)//相当于分解质因式的逆过程

{

if(!mark[i])

{

prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。

phi[i]=i-1;//当 i 是素数时 phi[i]=i-1

}

for(j=1;j<=tot;j++)

{

if(i*prime[j]>N) break;

mark[i*prime[j]]=1;//确定i*prime[j]不是素数

if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数

{

phi[i*prime[j]]=phi[i]*prime[j];break;

}

else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性

}

快速地得到欧拉函数值之后，前缀和什么的就是很简单的事情了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

const int N = 1000000;
int n;
int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合
bool mark[N+10];
void getphi()
{
    int i,j;
    phi[1]=1;
    for(i=2;i<=N;i++)//相当于分解质因式的逆过程
    {
        if(!mark[i])
        {
            prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
            phi[i]=i-1;//当 i 是素数时 phi[i]=i-1
        }
        for(j=1;j<=tot;j++)
        {
            if(i*prime[j]>N)  break;
            mark[i*prime[j]]=1;//确定i*prime[j]不是素数
            if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数
            {
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
        }
    }
}

long long phisum[1000006];

int main(){
    getphi();
    for (int i = 2; i <= 1000000; i++) {
        phisum[i] = phi[i] + phisum[i-1];
    }
    int q;
    while (cin >> q && q) {
        cout << phisum[q] << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

const int N = 1000000;

int n;

int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合

bool mark[N+10];

void getphi()

{

int i,j;

phi[1]=1;

for(i=2;i<=N;i++)//相当于分解质因式的逆过程

{

if(!mark[i])

{

prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。

phi[i]=i-1;//当 i 是素数时 phi[i]=i-1

}

for(j=1;j<=tot;j++)

{

if(i*prime[j]>N) break;

mark[i*prime[j]]=1;//确定i*prime[j]不是素数

if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数

{

phi[i*prime[j]]=phi[i]*prime[j];break;

}

else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性

}

long long phisum[1000006];

int main(){

getphi();

for (int i = 2; i <= 1000000; i++) {

phisum[i] = phi[i] + phisum[i-1];

}

int q;

while (cin >> q && q) {

cout << phisum[q] << endl;

}

return 0;

}