图论 – Page 2 – hahaschool

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;

}

POJ3352 Road Construction / POJ3177 Redundant Paths

August 20, 20152015-08-20hahaschoolLeave a comment

题意

给你一个联通图，问你最少要添加多少条边才能把这个图变成一个双联通图。

思路

非常经典的边双联通分量缩点问题。找出图中所有的边双联通分量，把这些分量各自收缩为一个点，节点之间若有边，一定是割边，这样就得到了一棵由边联通分量缩成的点和割边组成的树，把一个树变成双联通图要添加的最少边数是(r+1)/2其中r是这棵树的节点数量，这是一个蛮重要的结论。

找边联通分量的方法有好多，可以找到所有割边之后，对于每个点启动一次dfs，搜索中屏蔽掉所有割边，这样就可以收割所有的边双联通分量，也可以对于每个点直接启动一次tarjan算法，在函数返回的过程中，收割掉所有low值一样的节点就可以得到边双联通分量。这份代码使用的是后一种方案。

代码

两个题一个数据中有重边，一个没有，这份代码考虑了这个问题，所以连边都能顺利过，双倍经验。

//
//  POJ3552.cpp
//  playground
//
//  Copyright © 2015 Adam Chang. All rights reserved.
//

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

using namespace std;

const int MAXN = 1005;

int n = 0, m = 0;
vector<int> to[MAXN];
vector<int> to2[MAXN];

void add_edge(int a, int b){
    to[a].push_back(b);
    to[b].push_back(a);
}

void add_edge2(int a, int b){
    to2[a].push_back(b);
    to2[b].push_back(a);
}


void remove_duplicate(vector<int> *to){
    for (int i = 1; i <= n; i++) {
        sort(to[i].begin(), to[i].end());
        to[i].erase(unique(to[i].begin(), to[i].end()), to[i].end());
    }
}

int sdcc_belong[MAXN];
stack<int> sdcc_stk;
int sdcc_dfn[MAXN];
int sdcc_low[MAXN];
vector<vector<int> > sdcc;
int sdcc_cnt = 0;

void sdcc_tarjan(int cur, int par){
    sdcc_dfn[cur] = sdcc_low[cur] = sdcc_cnt++;
    sdcc_stk.push(cur);
    for (int i = 0; i < to[cur].size(); i++) {
        int nxt = to[cur][i];
        if (nxt == par) {
            continue;
        }
        if (!sdcc_dfn[nxt]) {
            //如果对面点还没有进入过，那就进去
            sdcc_tarjan(nxt, cur);
            sdcc_low[cur] = min(sdcc_low[cur], sdcc_low[nxt]);
        }else {
            //如果对面点进去过，那么考虑是不是回边，如果是的话要更新当前节点low值
            sdcc_low[cur] = min(sdcc_low[cur], sdcc_dfn[nxt]);
        }
    }
    //我们这样处理问题不会受重边影响，因为我们考虑的中心是边联通分量内部的点而非外部的割点，这样我们只需要关心当前这个点及其联通部分是不是有指向之前的点的回边就可以，只要没有回边，就说明边双联通分量已经走完了，可以收割
    if (sdcc_low[cur] == sdcc_dfn[cur]) {
        //当前节点及其联通部分没有任何指向父亲部分的回边了，可以收割和当前节点连着的所有节点为一个双联通分量了
        //generate sdcc
        int last;
        sdcc.push_back(vector<int>());
        int sdccid = (int)sdcc.size();
        do{
            last = sdcc_stk.top();
            sdcc_stk.pop();
            sdcc[sdccid-1].push_back(last);
            sdcc_belong[last] = sdccid;
        }while (cur != last);
    }
}

void get_sdcc(){
    memset(sdcc_belong, 0, sizeof(sdcc_belong));
    while (!sdcc_stk.empty()) {
        sdcc_stk.pop();
    }
    memset(sdcc_dfn, 0, sizeof(sdcc_dfn));
    memset(sdcc_low, 0, sizeof(sdcc_low));
    sdcc.clear();
    sdcc_cnt = 0;

    for (int i = 1; i <= n; i++) {
        if (!sdcc_dfn[i]) {
            sdcc_tarjan(i,0);
        }
    }
}

int main(){
    scanf(" %d %d",&n, &m);
    for (int i = 1; i <= n; i++) {
        to[i].clear();
    }
    for (int i = 1; i <= m; i++) {
        int a = 0, b = 0;
        scanf(" %d %d",&a, &b);
        add_edge(a, b);
    }
    get_sdcc();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < to[i].size(); j++) {
            if (sdcc_belong[to[i][j]] != sdcc_belong[i]) {
                add_edge2(sdcc_belong[to[i][j]], sdcc_belong[i]);
            }
        }
    }
    remove_duplicate(to2);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (to2[i].size() == 1) {
            res++;
        }
    }
    cout << (res+1)/2 << endl;
    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

128

129

130

131

132

133

// POJ3552.cpp

// playground

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <cmath>

using namespace std;

const int MAXN = 1005;

int n = 0, m = 0;

vector<int> to[MAXN];

vector<int> to2[MAXN];

void add_edge(int a, int b){

to[a].push_back(b);

to[b].push_back(a);

}

void add_edge2(int a, int b){

to2[a].push_back(b);

to2[b].push_back(a);

}

void remove_duplicate(vector<int> *to){

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

sort(to[i].begin(), to[i].end());

to[i].erase(unique(to[i].begin(), to[i].end()), to[i].end());

}

int sdcc_belong[MAXN];

stack<int> sdcc_stk;

int sdcc_dfn[MAXN];

int sdcc_low[MAXN];

vector<vector<int> > sdcc;

int sdcc_cnt = 0;

void sdcc_tarjan(int cur, int par){

sdcc_dfn[cur] = sdcc_low[cur] = sdcc_cnt++;

sdcc_stk.push(cur);

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

int nxt = to[cur][i];

if (nxt == par) {

continue;

}

if (!sdcc_dfn[nxt]) {

//如果对面点还没有进入过，那就进去

sdcc_tarjan(nxt, cur);

sdcc_low[cur] = min(sdcc_low[cur], sdcc_low[nxt]);

}else {

//如果对面点进去过，那么考虑是不是回边，如果是的话要更新当前节点low值

sdcc_low[cur] = min(sdcc_low[cur], sdcc_dfn[nxt]);

}

//我们这样处理问题不会受重边影响，因为我们考虑的中心是边联通分量内部的点而非外部的割点，这样我们只需要关心当前这个点及其联通部分是不是有指向之前的点的回边就可以，只要没有回边，就说明边双联通分量已经走完了，可以收割

if (sdcc_low[cur] == sdcc_dfn[cur]) {

//当前节点及其联通部分没有任何指向父亲部分的回边了，可以收割和当前节点连着的所有节点为一个双联通分量了

//generate sdcc

int last;

sdcc.push_back(vector<int>());

int sdccid = (int)sdcc.size();

do{

last = sdcc_stk.top();

sdcc_stk.pop();

sdcc[sdccid-1].push_back(last);

sdcc_belong[last] = sdccid;

}while (cur != last);

}

void get_sdcc(){

memset(sdcc_belong, 0, sizeof(sdcc_belong));

while (!sdcc_stk.empty()) {

sdcc_stk.pop();

}

memset(sdcc_dfn, 0, sizeof(sdcc_dfn));

memset(sdcc_low, 0, sizeof(sdcc_low));

sdcc.clear();

sdcc_cnt = 0;

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

if (!sdcc_dfn[i]) {

sdcc_tarjan(i,0);

}

int main(){

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

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

to[i].clear();

}

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

int a = 0, b = 0;

scanf(" %d %d",&a, &b);

add_edge(a, b);

}

get_sdcc();

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

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

if (sdcc_belong[to[i][j]] != sdcc_belong[i]) {

add_edge2(sdcc_belong[to[i][j]], sdcc_belong[i]);

}

remove_duplicate(to2);

int res = 0;

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

if (to2[i].size() == 1) {

res++;

}

cout << (res+1)/2 << endl;

return 0;

}

HDU4738 Caocao's Bridges

August 20, 20152015-08-20hahaschoolLeave a comment

题意

给出一个图，和一堆边，不保证没有重边，每一个边上携带者一个权值，现在问你能不能删去一条边，使图不再联通。可以的话删去权值最小的那条边，并且输出这个权值。

注意(坑点)

因为题意的特殊性，如果图本来就不联通，输出0.如果可以满足条件但最小的权值恰好是0，要输出1。

思路

删一个边把图裂开这种要求很明显就是找图的割边了。寻找割边是很典型的问题，应该使用tarjan算法，但是一定要注意重边对于找割边的影响(因为割边删掉后，图应该会裂开，但是如果有重边，删掉一条，还有一条，图显然不会裂开)，因此我们要对原来的方法稍作修改，首先是存图的方式，我们不能漏掉任意一条边，因此一个理想的方式就是链式前向星。链式前向星有一个很好用的特性，我们在创建无向边的时候实际上是创建了两条有向边，而这两条有向边在链式前向星的容器中的编号是相邻的，也就是说对于编号i的边i^1就是这条边对应的反向边，这样我们就可以非常方便地标记这条边是不是已经走过(vis_e[i] = vis_e[i^1] = true)。tarjan部分附带了注释。

代码

//
//  HDU4738.cpp
//  playground
//
//  Copyright (c) 2015 Adam Chang. All rights reserved.
//

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

using namespace std;

#define MAXN 1005
#define MAXE 2000005

struct EDGE
{
    int u, v, w;
    int next;
};

int first[MAXN], rear;
EDGE edge[MAXE];

void init(int n)
{
    memset(first, -1, sizeof(first[0])*(n+1));
    rear = 0;
}

void insert(int tu, int tv, int tw)
{
    edge[rear].u = tu;
    edge[rear].v = tv;
    edge[rear].w = tw;
    edge[rear].next = first[tu];
    first[tu] = rear++;
    edge[rear].u = tv;
    edge[rear].v = tu;
    edge[rear].w = tw;
    edge[rear].next = first[tv];
    first[tv] = rear++;
}


int pre[MAXN], low[MAXN];
bool vis_e[MAXE];      //是否访问了边
bool is_bridge[MAXE];  //是否是桥
int dfs_clock;
int res = 909303;
void dfs(int cur)
{
    pre[cur] = low[cur] = ++dfs_clock;
    for(int i = first[cur]; ~i; i = edge[i].next)
    {
        //便利以当前点出发的所有边
        int tv = edge[i].v;
        if(!pre[tv])
        {
            //如果这条边连接着的节点还没有访问过，那就进到这个节点里面
            vis_e[i] = vis_e[i^1] = true;
            dfs(tv);
            low[cur] = min(low[cur], low[tv]);
            if(pre[cur] < low[tv]){
                //当前边连着的这个节点处理完毕了，如果发现这个节点的low值还是比当前节点大，说明这个节点及其联通部分没有指向已访问任何节点的回边，也就是说割开当前这条边，这个节点以及其联通的部分就和当前节点裂开了，这条边也就理所当然的是割边
                is_bridge[i] = is_bridge[i^1] = true;
                res = min(res,edge[i].w);//更新答案用的
            }
        }
        else
            if(pre[tv] < pre[cur] && !vis_e[i])
            {
                //这里是如果当前这条边是一条回边，那么就要更新当前节点的low值了
                vis_e[i] = vis_e[i^1] = true;
                low[cur] = min(low[cur], pre[tv]);
            }
    }
}

void find_bridge(int n)
{
    res = 909303;
    dfs_clock = 0;
    memset(pre, 0, sizeof(pre[0])*(n+1));
    memset(vis_e, 0, sizeof(vis_e[0])*rear);
    memset(is_bridge, 0, sizeof(is_bridge[0])*rear);
    dfs(1);
}

int main(){
    int n = 0,m = 0;
    while (scanf(" %d %d",&n,&m) != EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        init(n);
        for (int i = 1; i <= m; i++) {
            int u = 0,v = 0,w = 0;
            scanf(" %d %d %d",&u,&v,&w);
            insert(u, v, w);
        }
        find_bridge(n);
        if (dfs_clock < n) {
            cout << 0 << endl;
        }else if (res == 909303) {
            cout << -1 << endl;
        }else if(res == 0){
            cout << 1 << endl;
        }else {
            cout << 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

// HDU4738.cpp

// playground

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <cmath>

using namespace std;

#define MAXN 1005

#define MAXE 2000005

struct EDGE

{

int u, v, w;

int next;

};

int first[MAXN], rear;

EDGE edge[MAXE];

void init(int n)

{

memset(first, -1, sizeof(first[0])*(n+1));

rear = 0;

}

void insert(int tu, int tv, int tw)

{

edge[rear].u = tu;

edge[rear].v = tv;

edge[rear].w = tw;

edge[rear].next = first[tu];

first[tu] = rear++;

edge[rear].u = tv;

edge[rear].v = tu;

edge[rear].w = tw;

edge[rear].next = first[tv];

first[tv] = rear++;

}

int pre[MAXN], low[MAXN];

bool vis_e[MAXE]; //是否访问了边

bool is_bridge[MAXE]; //是否是桥

int dfs_clock;

int res = 909303;

void dfs(int cur)

{

pre[cur] = low[cur] = ++dfs_clock;

for(int i = first[cur]; ~i; i = edge[i].next)

{

//便利以当前点出发的所有边

int tv = edge[i].v;

if(!pre[tv])

{

//如果这条边连接着的节点还没有访问过，那就进到这个节点里面

vis_e[i] = vis_e[i^1] = true;

dfs(tv);

low[cur] = min(low[cur], low[tv]);

if(pre[cur] < low[tv]){

//当前边连着的这个节点处理完毕了，如果发现这个节点的low值还是比当前节点大，说明这个节点及其联通部分没有指向已访问任何节点的回边，也就是说割开当前这条边，这个节点以及其联通的部分就和当前节点裂开了，这条边也就理所当然的是割边

is_bridge[i] = is_bridge[i^1] = true;

res = min(res,edge[i].w);//更新答案用的

}

else

if(pre[tv] < pre[cur] && !vis_e[i])

{

//这里是如果当前这条边是一条回边，那么就要更新当前节点的low值了

vis_e[i] = vis_e[i^1] = true;

low[cur] = min(low[cur], pre[tv]);

}

void find_bridge(int n)

{

res = 909303;

dfs_clock = 0;

memset(pre, 0, sizeof(pre[0])*(n+1));

memset(vis_e, 0, sizeof(vis_e[0])*rear);

memset(is_bridge, 0, sizeof(is_bridge[0])*rear);

dfs(1);

}

int main(){

int n = 0,m = 0;

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

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

break;

}

init(n);

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

int u = 0,v = 0,w = 0;

scanf(" %d %d %d",&u,&v,&w);

insert(u, v, w);

}

find_bridge(n);

if (dfs_clock < n) {

cout << 0 << endl;

}else if (res == 909303) {

cout << -1 << endl;

}else if(res == 0){

cout << 1 << endl;

}else {

cout << res << endl;

}

SGU 101 Domino

April 07, 20152015-04-07hahaschoolLeave a comment

题意

给你一堆骨牌，每张骨牌正反两面各有一个0～6范围内的数字，你要做的是确定一种骨牌的排列方式和骨牌的正反似的相邻的两个骨牌的面数字一样。

思路

这种链接多个物体，物体之间通过公共部分链接，这种题是可以转换成图论题做的。那么这个题应该怎么转换？
我们建立0～6这7个节点，每张骨牌就可以看作是链接骨牌上两个数的边，我们要做的就是找到一个路径使得我们可以“一笔”走过所有的边，其实这个叫欧拉通路。
关于欧拉通路，欧拉回路的更多细节，可以参看http://haha.school/guanyuoulahuiluheoulalujing/。
找出欧拉回路的方法就是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>

using namespace std;

vector<pair<int, int> > ljb[7];//first to second id
int n = 0;

bool vis[105];
int res[105];
int now = 0;
void dfs(int currNode){
    for (int i = 0; i < ljb[currNode].size(); i++) {
        if(!vis[abs(ljb[currNode][i].second)]){
            vis[abs(ljb[currNode][i].second)] = true;
            dfs(ljb[currNode][i].first);
            now++;
            res[now] = ljb[currNode][i].second;
        }
    }
}

int main(){
    for(int i = 0;i <= 6;i++)
    ljb[i].clear();
    scanf(" %d",&n);
    int oddpnt = 0;
    for(int i = 1;i <= n;i++){
        int a = 0,b = 0;
        scanf(" %d %d",&a,&b);
        oddpnt = a;
        ljb[a].push_back(make_pair(b,i));
        ljb[b].push_back(make_pair(a,-i));
    }
    int oddcnt = 0,evencnt = 0;
    for (int i = 0; i <= 6; i++) {
            if (ljb[i].size()%2) {
                oddcnt++;
                oddpnt = i;
            }else{
                evencnt++;
            }
    }
    if (evencnt == 7 || oddcnt == 2) {
        memset(vis,0,sizeof(vis));
        memset(res, 0, sizeof(res));
        now = 0;
        dfs(oddpnt);
        if (now != n) {
            printf("No solution\n");
        }else{
            for (int i = n; i >= 1; i--) {
                if (res[i] > 0) {
                    printf("%d +\n",res[i]);
                }else{
                    printf("%d -\n",abs(res[i]));
                }
            }

        }
    }else{
        printf("No solution\n");
    }

    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>

using namespace std;

vector<pair<int, int> > ljb[7];//first to second id

int n = 0;

bool vis[105];

int res[105];

int now = 0;

void dfs(int currNode){

for (int i = 0; i < ljb[currNode].size(); i++) {

if(!vis[abs(ljb[currNode][i].second)]){

vis[abs(ljb[currNode][i].second)] = true;

dfs(ljb[currNode][i].first);

now++;

res[now] = ljb[currNode][i].second;

}

int main(){

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

ljb[i].clear();

scanf(" %d",&n);

int oddpnt = 0;

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

int a = 0,b = 0;

scanf(" %d %d",&a,&b);

oddpnt = a;

ljb[a].push_back(make_pair(b,i));

ljb[b].push_back(make_pair(a,-i));

}

int oddcnt = 0,evencnt = 0;

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

if (ljb[i].size()%2) {

oddcnt++;

oddpnt = i;

}else{

evencnt++;

}

if (evencnt == 7 || oddcnt == 2) {

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

memset(res, 0, sizeof(res));

now = 0;

dfs(oddpnt);

if (now != n) {

printf("No solution\n");

}else{

for (int i = n; i >= 1; i--) {

if (res[i] > 0) {

printf("%d +\n",res[i]);

}else{

printf("%d -\n",abs(res[i]));

}

}else{

printf("No solution\n");

}

return 0;

}

关于欧拉回路和欧拉路径

April 07, 20152015-04-07hahaschoolOne Comment

请留意本文转载自http://www.cppblog.com/abilitytao/archive/2010/07/26/121319.html

如果侵犯了您（原作者）的权益请联系我删除，谢谢。

定义：
欧拉回路：每条边恰好只走一次，并能回到出发点的路径
欧拉路径：经过每一条边一次，但是不要求回到起始点

①首先看欧拉回路存在性的判定：

一、无向图
每个顶点的度数都是偶数，则存在欧拉回路。

二、有向图（所有边都是单向的）
每个节顶点的入度都等于出度，则存在欧拉回路。

三.混合图欧拉回路
混合图欧拉回路用的是网络流。
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？查看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
②.欧拉路径存在性的判定

一。无向图
一个无向图存在欧拉路径，当且仅当该图所有顶点的度数为偶数或者除了两个度数为奇数外其余的全是偶数。

二。有向图
一个有向图存在欧拉路径，当且仅当该图所有顶点的度数为零或者一个顶点的度数为1，另一个度数为-1，其他顶点的度数为0。

三。混合图欧拉路径
其实整篇文章只有这部分是我写的哈，灰常不好意思，只是网上的同志们写的太好了，实在没有必要重复劳动，不知道大家有没有发现，求欧拉路径的第一步一定是求欧拉回路，在混合图上也不例外，如何判断混合图欧拉回路问题的存在性呢？首先，我们用上文所说的方法判断该图是否存在欧拉回路，如果存在，欧拉路径一定存在。如果欧拉回路不存在，那么我们枚举欧拉路径的起点和终点，连接一条无向边，然后再用最大流判断是否存在欧拉回路即可。

SGU 103 Traffic Lights

March 22, 20152015-03-22hahaschoolLeave a comment

题意

http://www.nocow.cn/index.php/Translate:Sgu/103
翻译版，这里不重复劳动了

思路

这个题的可怕之处不是有多难想，而是虽然基本模型很简单就是图上最短路，但是这回有许多许多的限制条件。
正确地计算当前灯的状态是这个题最大的难点，我采用的方法是（其实我写跪了，李大神给我捞上来的）：首先把到这个路口已经消耗的时间减去题目给的初始时间，我叫他有效时间，接下来把这个有效时间模上两种颜色的灯持续时间之和，剩下的时间是对灯的状态真正有影响的时间，接下来分别脑内模拟一下站在这个路灯时如果是紫色最后会怎么变，如果是蓝色会怎么变，然后基本就可以写出这个时间和最终颜色的关系了，还可以得到最终这个颜色还能再持续多长时间，这两条非常重要，一定要搞对。
接下来的难点就是计算从当前点移动到下一个点之前等待两点灯的颜色同步的时间，算这个就要依赖于上面的两个值：当前颜色和当前颜色还剩多长时间，假设我们要从A点移动到B，已经走了tim时间，那么我们就要分别计算A点和B点在tim时的这两个数据，然后如果AB在tim时颜色正好相等，那么无需等待直接通行，所以等待时间为0，如果颜色不同呢？只要看A和B哪个剩余的时间短，这个就是等待时间了。要是剩余的时间又一样？那就要脑内模拟一下了，然后发现我们可以再比较A的下一颜色和B的下一颜色谁的持续时间短，等待时间就是剩余时间＋最短的持续时间。如果下一个颜色还一样，那就比较下下个颜色。要是还一样？对不起，hehe了，走别的吧～（所以说这个题很sxbk)
接下来是最段路部分，我们把权值设定为走到这个点要花多少时间，从当前点走到下一个点时，下一个点的可能值就是(当前点已用时间+等待两个点的灯同步的时间+路上消耗的时间)，以此为基准进行松弛操作。

接下来上代码

#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>

using namespace std;

int str = 0,ter = 0;
int n = 0,m = 0;

struct edgeType{
    int to;
    int cost;
    edgeType(){
        to = 0;
        cost = 0;
    }
    edgeType(int ito,int icost){
        to = ito;
        cost = icost;
    }
};

struct vertexType{
    char color;
    int init;
    int blue;
    int purple;
    int pre;//for backtracking
    int dis;
    vector<edgeType> edge;
    vertexType(){
        color = 0;
        init = 0;
        blue = 0;
        purple = 0;
        pre = 0;
        dis = 0x3f3f3f3f;
        edge.clear();
    }
} vertex[305];

char getColor(int timepast,int a){
    vertexType &av = vertex[a];
    int atime = (timepast % (av.blue+av.purple)) - av.init;
    if (av.color == 'P') {
        if (atime < 0) {
            return 'P';
        }else if(atime < av.blue){
            return 'B';
        }else{
            return 'P';
        }
    }else{
        if (atime < 0) {
            return 'B';
        }else if(atime < av.purple){
            return 'P';
        }else{
            return 'B';
        }
    }
}
char getTime(int timepast,int a){
    vertexType &av = vertex[a];
    int atime = (timepast %(av.blue+av.purple)) - av.init;
    if (av.color == 'P') {
        if (atime < 0) {
            return -atime;
        }else if(atime < av.blue){
            return av.blue-atime;
        }else{
            return av.blue+av.purple-atime;
        }
    }else{
        if (atime < 0) {
            return -atime;
        }else if(atime < av.purple){
            return av.purple-atime;
        }else{
            return av.blue+av.purple-atime;
        }
    }
}

int waitTime(int a,int b){
    //from a to b
    vertexType &av = vertex[a];
    vertexType &bv = vertex[b];
    int atime = getTime(av.dis, a);
    int btime = getTime(av.dis, b);
    char acolor = getColor(av.dis,a);
    char bcolor = getColor(av.dis,b);
    if (acolor == bcolor) {
        return 0;
    }
    if (abs(atime - btime)) {
        return min(atime,btime);
    }else if(acolor == 'P'){
        if (abs(av.blue-bv.purple)) {
            return atime+min(av.blue,bv.purple);
        }else if(abs(av.purple-bv.blue)){
            return atime+av.blue+min(av.purple,bv.blue);
        }else{
            return -1;
        }
    }else if(acolor == 'B'){
        if (abs(av.purple-bv.blue)) {
            return atime+min(av.purple,bv.blue);
        }else if(abs(av.blue-bv.purple)){
            return atime+av.purple+min(av.blue,bv.purple);
        }else{
            return -1;
        }
    }else{
        return -1;
    }
}

struct cmp{
    bool operator () (int a,int b){
        return vertex[a].dis > vertex[b].dis;
    }
};

void dijkstra(){
    vertex[str].dis = 0;
    priority_queue<int,vector<int>,cmp> q;
    q.push(str);
    bool vis[305];
    memset(vis, 0, sizeof(vis));
    while (!q.empty()) {
        int nown = q.top();
        q.pop();
        vis[nown] = true;
        vertexType &nowv = vertex[nown];
        for (int i = 0; i < nowv.edge.size(); i++) {
            int nextn = nowv.edge[i].to;
            vertexType &nextv = vertex[nextn];
            if (vis[nextn]) {
                continue;
            }
            int wait = waitTime(nown,nextn);
            if (wait == -1) {
                continue;
            }
            if (wait + nowv.dis + nowv.edge[i].cost < nextv.dis) {
                //relax
                nextv.dis = wait + nowv.dis + nowv.edge[i].cost;
                nextv.pre = nown;
                q.push(nextn);
            }
        }
    }

}



int main(){
    scanf(" %d %d %d %d",&str,&ter,&n,&m);
    for (int i = 1; i <= n; i++) {
        scanf(" %c %d %d %d",&vertex[i].color,&vertex[i].init,&vertex[i].blue,&vertex[i].purple);
    }
    for (int i = 1; i <= m; i++) {
        int a = 0,b = 0,c = 0;
        scanf(" %d %d %d",&a,&b,&c);
        vertex[a].edge.push_back(edgeType(b,c));
        vertex[b].edge.push_back(edgeType(a,c));
    }
    dijkstra();
    if (vertex[ter].dis == 0x3f3f3f3f) {
        printf("0\n");
        return 0;
    }
    printf("%d\n",vertex[ter].dis);
    stack<int> path;
    int curr = ter;
    while (curr) {
        path.push(curr);
        curr = vertex[curr].pre;
    }
    while (path.size()>1) {
        printf("%d ",path.top());
        path.pop();
    }
    printf("%d\n",path.top());
    path.pop();

    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

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

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

#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>

using namespace std;

int str = 0,ter = 0;

int n = 0,m = 0;

struct edgeType{

int to;

int cost;

edgeType(){

to = 0;

cost = 0;

}

edgeType(int ito,int icost){

to = ito;

cost = icost;

}

};

struct vertexType{

char color;

int init;

int blue;

int purple;

int pre;//for backtracking

int dis;

vector<edgeType> edge;

vertexType(){

color = 0;

init = 0;

blue = 0;

purple = 0;

pre = 0;

dis = 0x3f3f3f3f;

edge.clear();

}

} vertex[305];

char getColor(int timepast,int a){

vertexType &av = vertex[a];

int atime = (timepast % (av.blue+av.purple)) - av.init;

if (av.color == 'P') {

if (atime < 0) {

return 'P';

}else if(atime < av.blue){

return 'B';

}else{

return 'P';

}

}else{

if (atime < 0) {

return 'B';

}else if(atime < av.purple){

return 'P';

}else{

return 'B';

}

char getTime(int timepast,int a){

vertexType &av = vertex[a];

int atime = (timepast %(av.blue+av.purple)) - av.init;

if (av.color == 'P') {

if (atime < 0) {

return -atime;

}else if(atime < av.blue){

return av.blue-atime;

}else{

return av.blue+av.purple-atime;

}

}else{

if (atime < 0) {

return -atime;

}else if(atime < av.purple){

return av.purple-atime;

}else{

return av.blue+av.purple-atime;

}

int waitTime(int a,int b){

//from a to b

vertexType &av = vertex[a];

vertexType &bv = vertex[b];

int atime = getTime(av.dis, a);

int btime = getTime(av.dis, b);

char acolor = getColor(av.dis,a);

char bcolor = getColor(av.dis,b);

if (acolor == bcolor) {

return 0;

}

if (abs(atime - btime)) {

return min(atime,btime);

}else if(acolor == 'P'){

if (abs(av.blue-bv.purple)) {

return atime+min(av.blue,bv.purple);

}else if(abs(av.purple-bv.blue)){

return atime+av.blue+min(av.purple,bv.blue);

}else{

return -1;

}

}else if(acolor == 'B'){

if (abs(av.purple-bv.blue)) {

return atime+min(av.purple,bv.blue);

}else if(abs(av.blue-bv.purple)){

return atime+av.purple+min(av.blue,bv.purple);

}else{

return -1;

}

}else{

return -1;

}

struct cmp{

bool operator () (int a,int b){

return vertex[a].dis > vertex[b].dis;

}

};

void dijkstra(){

vertex[str].dis = 0;

priority_queue<int,vector<int>,cmp> q;

q.push(str);

bool vis[305];

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

while (!q.empty()) {

int nown = q.top();

q.pop();

vis[nown] = true;

vertexType &nowv = vertex[nown];

for (int i = 0; i < nowv.edge.size(); i++) {

int nextn = nowv.edge[i].to;

vertexType &nextv = vertex[nextn];

if (vis[nextn]) {

continue;

}

int wait = waitTime(nown,nextn);

if (wait == -1) {

continue;

}

if (wait + nowv.dis + nowv.edge[i].cost < nextv.dis) {

//relax

nextv.dis = wait + nowv.dis + nowv.edge[i].cost;

nextv.pre = nown;

q.push(nextn);

}

int main(){

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

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

scanf(" %c %d %d %d",&vertex[i].color,&vertex[i].init,&vertex[i].blue,&vertex[i].purple);

}

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

int a = 0,b = 0,c = 0;

scanf(" %d %d %d",&a,&b,&c);

vertex[a].edge.push_back(edgeType(b,c));

vertex[b].edge.push_back(edgeType(a,c));

}

dijkstra();

if (vertex[ter].dis == 0x3f3f3f3f) {

printf("0\n");

return 0;

}

printf("%d\n",vertex[ter].dis);

stack<int> path;

int curr = ter;

while (curr) {

path.push(curr);

curr = vertex[curr].pre;

}

while (path.size()>1) {

printf("%d ",path.top());

path.pop();

}

printf("%d\n",path.top());

path.pop();

return 0;

}

CodeForces 475B Strongly Connected City

March 11, 20152015-03-11hahaschoolLeave 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>

using namespace std;

vector<int> ljb[404];
bool vis[10005];
bool instk[10005];
int dfn[10005];
int low[10005];
int tim = 0;
stack<int> stk;
vector<vector<int> > ccs;

void dfs(int currNode){
    vis[currNode] = true;
    dfn[currNode] = low[currNode] = tim++;
    stk.push(currNode);
    instk[currNode] = true;
    vector<int> now = ljb[currNode];
    for (int i = 0;i < now.size(); i++) {
        if (!vis[now[i]]) {
            dfs(now[i]);
            low[currNode] = min(low[currNode],low[now[i]]);
        }else if (instk[now[i]]) {
            low[currNode] = min(low[currNode],dfn[now[i]]);
        }
    }
    if (dfn[currNode] == low[currNode]) {
        int tmp = 0;
        vector<int> res;
        while (currNode != tmp) {
            tmp = stk.top();
            res.push_back(tmp);
            //cout << tmp << "~";
            stk.pop();
            instk[tmp] = false;
        }
        //sort(res.begin(),res.end());
        ccs.push_back(res);
        //cout << endl;
    }
}


int main(){
    int n = 0,m = 0;
    scanf(" %d %d",&n,&m);
    for (int i = 1; i <= n*m; i++) {
        ljb[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        char way = 0;
        scanf(" %c",&way);
        if (way == '>') {
            for (int j = 1; j < m; j++) {
                ljb[(i-1)*m+j].push_back((i-1)*m+j+1);
            }
        }else{
            for (int j = m; j > 1; j--) {
                ljb[(i-1)*m+j].push_back((i-1)*m+j-1);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        char way = 0;
        scanf(" %c",&way);
        if (way == '^') {
            for (int j = n; j > 1; j--) {
                ljb[(j-1)*m+i].push_back((j-2)*m+i);
            }
        }else{
            for (int j = 1;j < n; j++) {
                ljb[(j-1)*m+i].push_back((j)*m+i);
            }
        }
    }

    dfs(1);
    for (int i = 0; i < ccs.size(); i++) {
        if (ccs[i].size() == n*m) {
            printf("YESn");
            return 0;
        }
    }
    printf("NOn");
    return 0;

    return 0;
}

100

101

102

#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>

using namespace std;

vector<int> ljb[404];

bool vis[10005];

bool instk[10005];

int dfn[10005];

int low[10005];

int tim = 0;

stack<int> stk;

vector<vector<int> > ccs;

void dfs(int currNode){

vis[currNode] = true;

dfn[currNode] = low[currNode] = tim++;

stk.push(currNode);

instk[currNode] = true;

vector<int> now = ljb[currNode];

for (int i = 0;i < now.size(); i++) {

if (!vis[now[i]]) {

dfs(now[i]);

low[currNode] = min(low[currNode],low[now[i]]);

}else if (instk[now[i]]) {

low[currNode] = min(low[currNode],dfn[now[i]]);

}

if (dfn[currNode] == low[currNode]) {

int tmp = 0;

vector<int> res;

while (currNode != tmp) {

tmp = stk.top();

res.push_back(tmp);

//cout << tmp << "~";

stk.pop();

instk[tmp] = false;

}

//sort(res.begin(),res.end());

ccs.push_back(res);

//cout << endl;

}

int main(){

int n = 0,m = 0;

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

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

ljb[i].clear();

}

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

char way = 0;

scanf(" %c",&way);

if (way == '>') {

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

ljb[(i-1)*m+j].push_back((i-1)*m+j+1);

}

}else{

for (int j = m; j > 1; j--) {

ljb[(i-1)*m+j].push_back((i-1)*m+j-1);

}

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

char way = 0;

scanf(" %c",&way);

if (way == '^') {

for (int j = n; j > 1; j--) {

ljb[(j-1)*m+i].push_back((j-2)*m+i);

}

}else{

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

ljb[(j-1)*m+i].push_back((j)*m+i);

}

dfs(1);

for (int i = 0; i < ccs.size(); i++) {

if (ccs[i].size() == n*m) {

printf("YESn");

return 0;

}

printf("NOn");

return 0;

}

强联通分量的题，建图搞定了就搞定了。关于scc的算法可以翻我的图论标签找一下我写的一篇tarjan算法总结。

HDU 1142 A Walk Through the Forest

January 30, 20152015-01-30hahaschoolLeave a comment

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

using namespace std;
#define MAXN 0x3f3f3f3f

int cost[1005][1005];
int dis[1005];
bool vis[1005];
void dijkstra(int n){
    memset(dis, MAXN, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[2] = 0;
    while (true) {
        int cur = 0,mindis = MAXN;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                continue;
            }
            if (dis[i] < mindis) {
                mindis = dis[i];
                cur = i;
            }
        }
        if (!cur) {
            break;
        }
        vis[cur] = true;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                continue;
            }
            if (cost[cur][i]!=MAXN && dis[cur]+cost[cur][i] < dis[i]) {
                dis[i] = cost[cur][i]+dis[cur];
            }
        }
    }
}

int cnt[1005];
int dfs(int currNode,int n){
    if (cnt[currNode] != -1) {
        return cnt[currNode];
    }
    if (currNode == 2) {
        return 1;
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (cost[currNode][i] == MAXN) {
            continue;
        }
        if (dis[currNode] > dis[i]) {
            sum += dfs(i,n);
        }
    }
    return cnt[currNode] = sum;
}


int main(){
    int n = 0, m = 0;
    while (scanf(" %d",&n) != EOF && n) {
        scanf(" %d",&m);
        memset(cost, MAXN, sizeof(cost));
        for (int i = 1; i <= n; i++) {
            cost[i][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            int a = 0,b = 0,c = 0;
            scanf(" %d %d %d",&a,&b,&c);
            cost[a][b] = c;
            cost[b][a] = c;
        }
        dijkstra(n);
        memset(cnt, -1, sizeof(cnt));
        cout << dfs(1,n) << endl;
    }


    return 0;
}

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

#define MAXN 0x3f3f3f3f

int cost[1005][1005];

int dis[1005];

bool vis[1005];

void dijkstra(int n){

memset(dis, MAXN, sizeof(dis));

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

dis[2] = 0;

while (true) {

int cur = 0,mindis = MAXN;

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

if (vis[i]) {

continue;

}

if (dis[i] < mindis) {

mindis = dis[i];

cur = i;

}

if (!cur) {

break;

}

vis[cur] = true;

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

if (vis[i]) {

continue;

}

if (cost[cur][i]!=MAXN && dis[cur]+cost[cur][i] < dis[i]) {

dis[i] = cost[cur][i]+dis[cur];

}

int cnt[1005];

int dfs(int currNode,int n){

if (cnt[currNode] != -1) {

return cnt[currNode];

}

if (currNode == 2) {

return 1;

}

int sum = 0;

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

if (cost[currNode][i] == MAXN) {

continue;

}

if (dis[currNode] > dis[i]) {

sum += dfs(i,n);

}

return cnt[currNode] = sum;

}

int main(){

int n = 0, m = 0;

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

scanf(" %d",&m);

memset(cost, MAXN, sizeof(cost));

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

cost[i][i] = 0;

}

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

int a = 0,b = 0,c = 0;

scanf(" %d %d %d",&a,&b,&c);

cost[a][b] = c;

cost[b][a] = c;

}

dijkstra(n);

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

cout << dfs(1,n) << endl;

}

return 0;

}

这个题数据好像有坑，如果用vector实现的邻接表会WAWAWA。。。嗯

然后题意那个sxbk的英语也是醉人，要是理解成最短路有多少条就哈哈了，应该是使到2节点的最短距离递减的节点序列有多少条。

然后你理解对了题意，又很脸好地用了邻接矩阵，嗯，估计还会T一阵子，原因是这个题还要卡DFS的优化问题，要使用记忆化搜索。

把这三点都注意了就能A了。（如果数据不坑，其实真是个好题）

HDU 1874 畅通工程续

January 25, 20152015-01-25hahaschoolLeave a comment

#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <vector>
#include <queue>
#define MAXN 0x3f3f3f3f
//Dijasktra
using namespace std;
int roadmap[205][205];
bool vis[205];
int sr[205];
int main(){
    int n = 0,m = 0;

    while (cin >> n >> m && m+n) {
        memset(roadmap, 0x3f3f, sizeof(roadmap));
        memset(sr, 0x3f3f, sizeof(sr));
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            roadmap[i][i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            int a = 0,b = 0,c = 0;
            cin >> a >> b >> c;
            if (roadmap[a][b] > c){
            roadmap[a][b] = c;
            roadmap[b][a] = c;
            }
        }
        int s = 0,t = 0;
        cin >> s >> t;
        sr[s] = 0;
        while (true) {
            int i = -1;
            for (int q = 0; q < n; q++) {
                if (!vis[q]) {
                    if (i == -1 || sr[q] < sr[i]) {
                        i = q;
                    }
                }
            }
            if (i == -1) break;
            for (int q = 0; q < n; q++){
                sr[q] = min(sr[i]+roadmap[i][q],sr[q]);
            }
            vis[i] = true;
        }
        if (sr[t] == MAXN) {
            sr[t] = -1;
        }
        cout << sr[t] << endl;


    }
    return 0;
}

#include <cmath>

#include <iostream>

#include <cstring>

#include <string>

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <vector>

#include <queue>

#define MAXN 0x3f3f3f3f

//Dijasktra

using namespace std;

int roadmap[205][205];

bool vis[205];

int sr[205];

int main(){

int n = 0,m = 0;

while (cin >> n >> m && m+n) {

memset(roadmap, 0x3f3f, sizeof(roadmap));

memset(sr, 0x3f3f, sizeof(sr));

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

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

roadmap[i][i] = 0;

}

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

int a = 0,b = 0,c = 0;

cin >> a >> b >> c;

if (roadmap[a][b] > c){

roadmap[a][b] = c;

roadmap[b][a] = c;

}

int s = 0,t = 0;

cin >> s >> t;

sr[s] = 0;

while (true) {

int i = -1;

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

if (!vis[q]) {

if (i == -1 || sr[q] < sr[i]) {

i = q;

}

if (i == -1) break;

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

sr[q] = min(sr[i]+roadmap[i][q],sr[q]);

}

vis[i] = true;

}

if (sr[t] == MAXN) {

sr[t] = -1;

}

cout << sr[t] << endl;

}

return 0;

}

这是个裸的最短路问题，随便怎么搞都行。

这里用的是没有堆优化的dijkstra。

POJ 1062 昂贵的聘礼

January 25, 20152015-01-25hahaschoolLeave a comment

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

 using namespace std;

#define MAXN 0x3f3f3f3f

struct edgeType{
    int to;
    int cost;
    edgeType(int ito,int icost){
        to = ito;
        cost = icost;
    }
};

struct vertexType{
    vector<edgeType> edge;
    int cost;
    int level;
    vertexType(int icost,int ilevel){
        edge.clear();
        cost = icost;
        level = ilevel;
    }
};

int main(){
    int m = 0,n = 0;
    while (cin >> m >> n) {
        vector<vertexType> vertex;
        for (int i = 0; i < n; i++) {
            int vcost,vlevel,vsub;
            cin >> vcost >> vlevel >> vsub;
            vertexType now(vcost,vlevel);
            while (vsub--) {
                int to,cost;
                cin >> to >> cost;
                edgeType tmp(to-1,cost);
                now.edge.push_back(tmp);
            }
            vertex.push_back(now);
        }

        int maxlv = vertex[0].level,minlv = vertex[0].level;
        bool vis[105];
        int dis[105];
        memset(vis, 0, sizeof(vis));
        memset(dis, 0x3f3f, sizeof(dis));
        dis[0] = vertex[0].cost;
        while (true) {
            int cur = -1;
            int mindis = MAXN;
            for (int i = 0; i < vertex.size(); i++) {
                if (vis[i]) {
                    continue;
                }
                if (dis[i] < mindis) {
                    mindis = dis[i];
                    cur = i;
                }
            }
            if (cur == -1) break;

            vertexType nowvertex = vertex[cur];
            vis[cur] = true;
            maxlv = max(nowvertex.level,maxlv);
            minlv = min(nowvertex.level,minlv);
            //int nowlv = nowvertex.level;
            for (int i = 0; i < vertex[cur].edge.size(); i++) {
                edgeType nextedge = vertex[cur].edge[i];
                vertexType nextvertex = vertex[nextedge.to];
                if (max(abs(maxlv-nextvertex.level),abs(minlv-nextvertex.level)) > m) {
                    continue;
                }
                int newcost = dis[cur] - nowvertex.cost + nextedge.cost + nextvertex.cost;
                if (newcost < dis[nextedge.to]) {
                    dis[nextedge.to] = newcost;
                }
            }
        }
        int res = MAXN;
        for (int i = 0; i < n; i++) {
            res = min(dis[i], res);
        }
        cout << res << endl;
    }

    return 0;
}

100

101

102

103

104

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

#define MAXN 0x3f3f3f3f

struct edgeType{

int to;

int cost;

edgeType(int ito,int icost){

to = ito;

cost = icost;

}

};

struct vertexType{

vector<edgeType> edge;

int cost;

int level;

vertexType(int icost,int ilevel){

edge.clear();

cost = icost;

level = ilevel;

}

};

int main(){

int m = 0,n = 0;

while (cin >> m >> n) {

vector<vertexType> vertex;

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

int vcost,vlevel,vsub;

cin >> vcost >> vlevel >> vsub;

vertexType now(vcost,vlevel);

while (vsub--) {

int to,cost;

cin >> to >> cost;

edgeType tmp(to-1,cost);

now.edge.push_back(tmp);

}

vertex.push_back(now);

}

int maxlv = vertex[0].level,minlv = vertex[0].level;

bool vis[105];

int dis[105];

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

memset(dis, 0x3f3f, sizeof(dis));

dis[0] = vertex[0].cost;

while (true) {

int cur = -1;

int mindis = MAXN;

for (int i = 0; i < vertex.size(); i++) {

if (vis[i]) {

continue;

}

if (dis[i] < mindis) {

mindis = dis[i];

cur = i;

}

if (cur == -1) break;

vertexType nowvertex = vertex[cur];

vis[cur] = true;

maxlv = max(nowvertex.level,maxlv);

minlv = min(nowvertex.level,minlv);

//int nowlv = nowvertex.level;

for (int i = 0; i < vertex[cur].edge.size(); i++) {

edgeType nextedge = vertex[cur].edge[i];

vertexType nextvertex = vertex[nextedge.to];

if (max(abs(maxlv-nextvertex.level),abs(minlv-nextvertex.level)) > m) {

continue;

}

int newcost = dis[cur] - nowvertex.cost + nextedge.cost + nextvertex.cost;

if (newcost < dis[nextedge.to]) {

dis[nextedge.to] = newcost;

}

int res = MAXN;

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

res = min(dis[i], res);

}

cout << res << endl;

}

return 0;

}

这个题是一个比较基准有些多的最短路（和之前那个Dirt挺像）。

（这里的cost就是dijkstra算法里面的dis值）每一次更新下一节点时，下一节点的cost值为（当前cost值－当前点权＋下一边边权＋下一点点权）；每一次到达节点后，都根据当前抽出的节点的地位值，更新当前走过节点的地位的最大最小值，等接下来更新临接节点时，如果下一节点的地位与当前最大最小值中任意一个只差绝对值>m就要抛弃。以这两个为基准，进行正常的dijkstra，然后从头到尾的扫一遍cost数组，把最小值输出来就是答案。