图论 – Page 3 – hahaschool

POJ 1135 Domino Effect

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 dis;
    vertexType(){
        edge.clear();
        dis = MAXN;
    }
};
vector<vertexType> vertex;

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

int main(){
    int n = 0,m = 0;
    int casecnt = 0;
    while (cin >> n >> m) {
        if (m == 0 && n == 0) {
            break;
        }
        casecnt++;
        vertex.clear();
        for (int i = 0; i <= n; i++) {
            vertex.push_back(vertexType());
        }
        for (int i = 0; i < m; i++) {
            int a = 0,b = 0,c = 0;
            cin >> a >> b >> c;
            vertex[a].edge.push_back(edgeType(b,c));
            vertex[b].edge.push_back(edgeType(a,c));
        }
        bool vis[502];
        memset(vis, 0, sizeof(vis));
        vertex[1].dis = 0;
        priority_queue<int,vector<int>,cmp> q;
        q.push(1);
        while (!q.empty()) {
            int cur = q.top();
            q.pop();
            vis[cur] = true;
            for (int i = 0; i < vertex[cur].edge.size(); i++) {
                edgeType nextedge = vertex[cur].edge[i];
                if (vis[nextedge.to]) {
                    continue;
                }
                if (vertex[nextedge.to].dis > vertex[cur].dis + nextedge.cost) {
                    vertex[nextedge.to].dis = vertex[cur].dis + nextedge.cost;
                    q.push(nextedge.to);
                }
            }
        }
        double res = 0;
        int pt1 = 1,pt2 = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < vertex[i].edge.size(); j++) {
                double terpos = ((double)vertex[i].dis + (double)vertex[vertex[i].edge[j].to].dis + (double)vertex[i].edge[j].cost)/2;
                double judge = max(terpos,max((double)vertex[i].dis,(double)vertex[vertex[i].edge[j].to].dis));
                if (judge > res) {
                    if (judge != vertex[i].dis && judge != vertex[vertex[i].edge[j].to].dis) {
                        res = judge;
                        pt1 = min(i,vertex[i].edge[j].to);
                        pt2 = max(i,vertex[i].edge[j].to);
                    }else if(judge == (double)vertex[i].dis){
                        res = vertex[i].dis;
                        pt1 = i,pt2 = i;
                    }else{
                        res = vertex[vertex[i].edge[j].to].dis;
                        pt1 = vertex[i].edge[j].to,pt2 = vertex[i].edge[j].to;
                    }
                }
            }
        }
        cout << "System #" << casecnt << endl;
        cout.setf(ios::fixed);
        cout << "The last domino falls after " << setprecision(1) << res << " seconds, ";
        cout.unsetf(ios::fixed);
        if (pt1 != pt2) {
            cout << "between key dominoes " << pt1 << " and " << pt2 << '.' << endl;
        }else{
            cout << "at key domino " << pt1 << '.' << endl;
        }
        cout << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

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

vertexType(){

edge.clear();

dis = MAXN;

}

};

vector<vertexType> vertex;

struct cmp{

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

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

}

};

int main(){

int n = 0,m = 0;

int casecnt = 0;

while (cin >> n >> m) {

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

break;

}

casecnt++;

vertex.clear();

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

vertex.push_back(vertexType());

}

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

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

cin >> a >> b >> c;

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

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

}

bool vis[502];

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

vertex[1].dis = 0;

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

q.push(1);

while (!q.empty()) {

int cur = q.top();

q.pop();

vis[cur] = true;

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

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

if (vis[nextedge.to]) {

continue;

}

if (vertex[nextedge.to].dis > vertex[cur].dis + nextedge.cost) {

vertex[nextedge.to].dis = vertex[cur].dis + nextedge.cost;

q.push(nextedge.to);

}

double res = 0;

int pt1 = 1,pt2 = 1;

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

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

double terpos = ((double)vertex[i].dis + (double)vertex[vertex[i].edge[j].to].dis + (double)vertex[i].edge[j].cost)/2;

double judge = max(terpos,max((double)vertex[i].dis,(double)vertex[vertex[i].edge[j].to].dis));

if (judge > res) {

if (judge != vertex[i].dis && judge != vertex[vertex[i].edge[j].to].dis) {

res = judge;

pt1 = min(i,vertex[i].edge[j].to);

pt2 = max(i,vertex[i].edge[j].to);

}else if(judge == (double)vertex[i].dis){

res = vertex[i].dis;

pt1 = i,pt2 = i;

}else{

res = vertex[vertex[i].edge[j].to].dis;

pt1 = vertex[i].edge[j].to,pt2 = vertex[i].edge[j].to;

}

cout << "System #" << casecnt << endl;

cout.setf(ios::fixed);

cout << "The last domino falls after " << setprecision(1) << res << " seconds, ";

cout.unsetf(ios::fixed);

if (pt1 != pt2) {

cout << "between key dominoes " << pt1 << " and " << pt2 << '.' << endl;

}else{

cout << "at key domino " << pt1 << '.' << endl;

}

cout << endl;

}

return 0;

}

题我就没读懂。。。

其实是这样，把每一个key domino当做节点，他们之间的骨牌数目当作边权，用dijkstra处理一下得到的就是骨牌倒道该节点的最短时间，接下来我们要考虑在中间倒完的情况。

如果在两个节点中间倒完的话，也就意味着从起点经过两个key domino到终点，左右两边走过的时间是一样的，所以我们可以用(dis[a]+dis[b]+edge.cost)/2这个就可以求出在两点之间倒完需要多少时间，我们把每条边都这样过一遍，如果求出来的这个值比左右两边节点的dis都大，说明倒在中间，如果正好等于某一个节点的dis值，就把那个节点当作终点，把所有的边都这样过完之后，找到最大的(dis[a]+dis[b]+edge.cost)/2对应的终止情形，就是答案。

HDU 3023 Dirt

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 MAXDEP 10000000

int dir[8][2] = {{1,1},{1,-1},{-1,1},{-1,-1},{1,0},{0,1},{-1,0},{0,-1}};
char board[1005][1005];
bool vis[1005][1005];
int m = 0,n = 0,cx = 0,cy = 0,rx = 0,ry = 0;

struct factorType{
    int shoe;
    int step;
    void fillmax(){
        shoe = MAXDEP,step = MAXDEP;
    }
} factor[1001][1001];
struct nodeType{
    int x;
    int y;
    bool operator < (nodeType b) const{
        if(factor[y][x].shoe == factor[b.y][b.x].shoe){
            return factor[y][x].step > factor[b.y][b.x].step;
        }
        return factor[y][x].shoe > factor[b.y][b.x].shoe;
    }
};


bool dijkstra(){
    nodeType init;
    priority_queue<nodeType> q;
    init.y = cy,init.x = cx;
    factor[cy][cx].shoe = 0;
    factor[cy][cx].step = 0;
    q.push(init);
    while (!q.empty()) {
        nodeType now;
        now = q.top();
        q.pop();
        if (now.y == ry && now.x == rx) return true;
        if(vis[now.y][now.x])continue;
        vis[now.y][now.x] = true;
        for (int i = 0; i < 8; i++) {
            nodeType tmp;
            tmp.y = now.y + dir[i][0];
            tmp.x = now.x + dir[i][1];
            if (tmp.x < 1 ||
                tmp.y < 1 ||
                tmp.x > n ||
                tmp.y > m ||
                vis[tmp.y][tmp.x]||
                board[tmp.y][tmp.x] == 0) {
                    continue;
                }
            if (factor[tmp.y][tmp.x].shoe > factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])) {
                factor[tmp.y][tmp.x].shoe = factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x]);
                factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1;
                q.push(tmp);
            }else if(factor[tmp.y][tmp.x].shoe == factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])
                     && (factor[tmp.y][tmp.x].step > factor[now.y][now.x].step+1)){
                factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1;
                q.push(tmp);
            }

        }
    }
    return false;
}

int main(){
    while (cin >> m >> n >> cy >> cx >> ry >> rx) {
        for (int i = 1; i <= m; i++) {//y dir
            getchar();
            for (int j = 1; j <= n; j++) {//x dir
                factor[i][j].fillmax();
                board[i][j] = getchar() - '0';
                vis[i][j] = false;
            }
        }

        if (dijkstra()) {
            cout << factor[ry][rx].step+1 << ' ' << factor[ry][rx].shoe << endl;
        }else{
            cout << 0 << ' ' << 0 << endl;
        }

    }
    return 0;
}

100

101

102

103

104

105

106

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

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

char board[1005][1005];

bool vis[1005][1005];

int m = 0,n = 0,cx = 0,cy = 0,rx = 0,ry = 0;

struct factorType{

int shoe;

int step;

void fillmax(){

shoe = MAXDEP,step = MAXDEP;

}

} factor[1001][1001];

struct nodeType{

int x;

int y;

bool operator < (nodeType b) const{

if(factor[y][x].shoe == factor[b.y][b.x].shoe){

return factor[y][x].step > factor[b.y][b.x].step;

}

return factor[y][x].shoe > factor[b.y][b.x].shoe;

}

};

bool dijkstra(){

nodeType init;

priority_queue<nodeType> q;

init.y = cy,init.x = cx;

factor[cy][cx].shoe = 0;

factor[cy][cx].step = 0;

q.push(init);

while (!q.empty()) {

nodeType now;

now = q.top();

q.pop();

if (now.y == ry && now.x == rx) return true;

if(vis[now.y][now.x])continue;

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

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

nodeType tmp;

tmp.y = now.y + dir[i][0];

tmp.x = now.x + dir[i][1];

if (tmp.x < 1 ||

tmp.y < 1 ||

tmp.x > n ||

tmp.y > m ||

vis[tmp.y][tmp.x]||

board[tmp.y][tmp.x] == 0) {

continue;

}

if (factor[tmp.y][tmp.x].shoe > factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])) {

factor[tmp.y][tmp.x].shoe = factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x]);

factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1;

q.push(tmp);

}else if(factor[tmp.y][tmp.x].shoe == factor[now.y][now.x].shoe + (board[now.y][now.x] != board[tmp.y][tmp.x])

&& (factor[tmp.y][tmp.x].step > factor[now.y][now.x].step+1)){

factor[tmp.y][tmp.x].step = factor[now.y][now.x].step+1;

q.push(tmp);

}

return false;

}

int main(){

while (cin >> m >> n >> cy >> cx >> ry >> rx) {

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

getchar();

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

factor[i][j].fillmax();

board[i][j] = getchar() - '0';

vis[i][j] = false;

}

if (dijkstra()) {

cout << factor[ry][rx].step+1 << ' ' << factor[ry][rx].shoe << endl;

}else{

cout << 0 << ' ' << 0 << endl;

}

return 0;

}

经过了极其艰辛（～3天）的过程终于把这个题肝出来了。

基本题型是最短路，采用dijkstra，利用优先队列做堆优化，之所以老不过是因为松弛写错了，当时错误地认为下一节点一定会换鞋，实际上应该判断一下是不是要换鞋，换鞋和不换鞋的松弛操作要分开进行。

ZOJ 3820 ACM 牡丹江 Building Fire Stations

January 19, 20152015-01-19hahaschoolLeave 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>

using namespace std;

#define MAXN 200005

struct nodeType{
    vector<int> to;
    int dep;
} node[MAXN];

void init_node(int n,bool clearljb){
    for (int i = 1; i <= n; i++) {
        if(clearljb) node[i].to.clear();
        node[i].dep = 1;
    }
}

vector<int> tdr;
int prevNode[MAXN];
bool vis[MAXN];
int bfs(int n,bool metaMode,int src,bool gentdr,int blocked){
    //0 for meta 1 for tdim
    //make blocked 0 if you do not want to split
    init_node(n,false);
    memset(vis, 0, sizeof(vis));
    memset(prevNode, 0, sizeof(prevNode));
    queue<int> q;
    q.push(src);
    int last = 0,maxdep = 0;
    while (!q.empty()) {
        nodeType &now = node[q.front()];
        vis[q.front()] = true;
        if (now.dep > maxdep) {
            maxdep = now.dep;
            last = q.front();
        }
        for (int i = 0; i < now.to.size(); i++) {
            if (vis[now.to[i]] || now.to[i] == blocked) {
                continue;
            }
            node[now.to[i]].dep = now.dep+1;
            q.push(now.to[i]);
            prevNode[now.to[i]] = q.front();
        }
        q.pop();
    }
    if (metaMode) {
        return last;
    }else {
        if (gentdr) {
            tdr.clear();
            int tmp = last;
            while (src != tmp) {
                tdr.push_back(tmp);
                tmp = prevNode[tmp];
            }
            tdr.push_back(src);
        }
        return maxdep;
    }
}

int main(){
    int casecnt;
    cin >> casecnt;
    while (casecnt--) {
        int n;
        cin >> n;
        init_node(n,true);
        for (int i = 1; i <= n-1; i++) {
            int a = 0,b = 0;
            scanf(" %d %d",&a,&b);
            node[a].to.push_back(b);
            node[b].to.push_back(a);
        }
        int seed = rand()%n+1;
        int meta = bfs(n, true, seed,false,0);
        int tdim = bfs(n, false, meta, true,0);

        int lans = 0,rans = 0,dis = 0;
        if (tdim % 2) {
            vector<int> origtdr = tdr;
            int center = (tdim-1)/2;
            //odd situ1
            int lmeta1 = bfs(n, true, origtdr[0], false, origtdr[center]);
            int ltdim1 = bfs(n, false, lmeta1, true, origtdr[center]);
            int lpos1 = tdr[ltdim1/2];
            int rmeta1 = bfs(n, true, origtdr[tdim-1], false, origtdr[center-1]);
            int rtdim1 = bfs(n, false, rmeta1, true, origtdr[center-1]);
            int rpos1 = tdr[rtdim1/2];
            int judge1 = max(ltdim1/2,rtdim1/2);

            //odd situ2
            int lmeta2  = bfs(n, true, origtdr[0], false, origtdr[center+1]);
            int ltdim2 = bfs(n, false, lmeta2, true, origtdr[center+1]);
            int lpos2 = tdr[ltdim2/2];
            int rmeta2 = bfs(n, true, origtdr[tdim-1], false,origtdr[center]);
            int rtdim2 = bfs(n, false, rmeta2, true, origtdr[center]);
            int rpos2 = tdr[rtdim2/2];
            int judge2 = max(ltdim2/2,rtdim2/2);

            //judge
            if (judge1 > judge2) {
                //2 is good
                lans = lpos2;
                rans = rpos2;
                dis = judge2;
            }else{
                //1 is good
                lans = lpos1;
                rans = rpos1;
                dis = judge1;
            }

        }else{
            //even situ
            int lend = tdr[tdim/2-1];
            int rend = tdr[tdim/2];
            //run left
            int lmeta = bfs(n, true, tdr[0], false,rend);
            //run right
            int rmeta = bfs(n, true, tdr[tdim-1], false, lend);
            int ltdim = bfs(n, false, lmeta, true, rend);
            lans = tdr[ltdim/2];
            int rtdim = bfs(n, false, rmeta, true, lend);
            rans = tdr[rtdim/2];
            dis = max(ltdim/2,rtdim/2);

        }
        cout << dis << ' ' << lans << ' ' << rans << ' ' << 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

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

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

using namespace std;

#define MAXN 200005

struct nodeType{

vector<int> to;

int dep;

} node[MAXN];

void init_node(int n,bool clearljb){

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

if(clearljb) node[i].to.clear();

node[i].dep = 1;

}

vector<int> tdr;

int prevNode[MAXN];

bool vis[MAXN];

int bfs(int n,bool metaMode,int src,bool gentdr,int blocked){

//0 for meta 1 for tdim

//make blocked 0 if you do not want to split

init_node(n,false);

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

memset(prevNode, 0, sizeof(prevNode));

queue<int> q;

q.push(src);

int last = 0,maxdep = 0;

while (!q.empty()) {

nodeType &now = node[q.front()];

vis[q.front()] = true;

if (now.dep > maxdep) {

maxdep = now.dep;

last = q.front();

}

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

if (vis[now.to[i]] || now.to[i] == blocked) {

continue;

}

node[now.to[i]].dep = now.dep+1;

q.push(now.to[i]);

prevNode[now.to[i]] = q.front();

}

q.pop();

}

if (metaMode) {

return last;

}else {

if (gentdr) {

tdr.clear();

int tmp = last;

while (src != tmp) {

tdr.push_back(tmp);

tmp = prevNode[tmp];

}

tdr.push_back(src);

}

return maxdep;

}

int main(){

int casecnt;

cin >> casecnt;

while (casecnt--) {

int n;

cin >> n;

init_node(n,true);

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

int a = 0,b = 0;

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

node[a].to.push_back(b);

node[b].to.push_back(a);

}

int seed = rand()%n+1;

int meta = bfs(n, true, seed,false,0);

int tdim = bfs(n, false, meta, true,0);

int lans = 0,rans = 0,dis = 0;

if (tdim % 2) {

vector<int> origtdr = tdr;

int center = (tdim-1)/2;

//odd situ1

int lmeta1 = bfs(n, true, origtdr[0], false, origtdr[center]);

int ltdim1 = bfs(n, false, lmeta1, true, origtdr[center]);

int lpos1 = tdr[ltdim1/2];

int rmeta1 = bfs(n, true, origtdr[tdim-1], false, origtdr[center-1]);

int rtdim1 = bfs(n, false, rmeta1, true, origtdr[center-1]);

int rpos1 = tdr[rtdim1/2];

int judge1 = max(ltdim1/2,rtdim1/2);

//odd situ2

int lmeta2 = bfs(n, true, origtdr[0], false, origtdr[center+1]);

int ltdim2 = bfs(n, false, lmeta2, true, origtdr[center+1]);

int lpos2 = tdr[ltdim2/2];

int rmeta2 = bfs(n, true, origtdr[tdim-1], false,origtdr[center]);

int rtdim2 = bfs(n, false, rmeta2, true, origtdr[center]);

int rpos2 = tdr[rtdim2/2];

int judge2 = max(ltdim2/2,rtdim2/2);

//judge

if (judge1 > judge2) {

//2 is good

lans = lpos2;

rans = rpos2;

dis = judge2;

}else{

//1 is good

lans = lpos1;

rans = rpos1;

dis = judge1;

}

}else{

//even situ

int lend = tdr[tdim/2-1];

int rend = tdr[tdim/2];

//run left

int lmeta = bfs(n, true, tdr[0], false,rend);

//run right

int rmeta = bfs(n, true, tdr[tdim-1], false, lend);

int ltdim = bfs(n, false, lmeta, true, rend);

lans = tdr[ltdim/2];

int rtdim = bfs(n, false, rmeta, true, lend);

rans = tdr[rtdim/2];

dis = max(ltdim/2,rtdim/2);

}

cout << dis << ' ' << lans << ' ' << rans << ' ' << endl;

}

return 0;

}

SXBK的一个题（对我现在的水平来说）

其实是这样，对于一棵树，在上面建1个消防站，最优位置在直径中心，建立两个消防站呢？其实可以把整个大树分成两个小树，在每个小树自己的直径的中心建立消防站就搞定了，在分树的时候，如果发生分歧（如果直径有奇数个点，就会出现这种分歧情况，如果有偶数个节点，中央节点有两个，直接从两个节点的中央裂开就行，不会产生分歧），这时候我把中央节点上连接的那些节点中除了直径上的两点之外的那些节点都叫做中立节点，我们只要进行两次讨论，一次把这些中立节点分入左半树，求出这种分法中左右半树的直径，然后把左右直径的最大值当成接下来判定哪个方法更好的基准（因为我们要的是最长距离的最小值），然后再把这些中立节点分入右半树，搞出相应的解，接下来我们比较刚才保存下来的基准，哪个小要哪种方案，这样我们就把最终的解搞出来了。

我觉得其实这种思路还可以推广，如果建立3个，4个乃至n个，我们也可以切割树求直径来搞。

然后切树是，我们可以通过把某个点“屏蔽”，来实现不会让dfs进入另一半子树的目的。

其实这个题还可以通过枚举大直径上的两点求出最优解来解决，思路也是比较清晰的。

HDU 4607 Park Visit

January 19, 20152015-01-19hahaschoolLeave 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>

using namespace std;

struct nodeType{
    int dep;
    vector<int> to;
} node[100005];

bool vis[100005];

inline void init_nodes(int n,bool clearljb){
    for (int i = 1; i <= n; i++) {
        node[i].dep = 1;
        if(clearljb) node[i].to.clear();
    }
}
int bfs(int n,int init,bool meta){
    init_nodes(n,false);
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(init);
    int res = 0;
    int last = 0;
    while (!q.empty()) {
        nodeType &now = node[q.front()];
        if (now.dep > res) {
            res = now.dep;
            last = q.front();
        }
        //cout << now.dep << endl;
        vis[q.front()] = true;
        q.pop();
        for (int i = 0; i < now.to.size(); i++) {
            if (vis[now.to[i]]) {
                continue;
            }
            node[now.to[i]].dep = now.dep+1;
            q.push(now.to[i]);
        }
    }
    if (meta) {
        return last;
    }
    return res;

}
int main(int argc, char *argv[]) {
    int casecnt;
    cin >> casecnt;
    while (casecnt--) {
        int n = 0,m = 0;
        cin >> n >> m;
        init_nodes(n,true);
        for (int i = 1; i <= n-1; i++) {
            int a = 0,b = 0;
            scanf(" %d %d",&a,&b);
            node[a].to.push_back(b);
            node[b].to.push_back(a);
        }
        int seed = (rand()%n)+1;
        int meta = bfs(n,seed,true);
        int diam = bfs(n, meta,false);

        for (int i = 1; i <= m; i++) {
            int k;
            scanf(" %d",&k);
            if (k <= diam) {
                printf("%dn",k-1);
            }else{
                printf("%dn",diam-1+2*(k-diam));
            }
        }
    }
    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>

using namespace std;

struct nodeType{

int dep;

vector<int> to;

} node[100005];

bool vis[100005];

inline void init_nodes(int n,bool clearljb){

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

node[i].dep = 1;

if(clearljb) node[i].to.clear();

}

int bfs(int n,int init,bool meta){

init_nodes(n,false);

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

queue<int> q;

q.push(init);

int res = 0;

int last = 0;

while (!q.empty()) {

nodeType &now = node[q.front()];

if (now.dep > res) {

res = now.dep;

last = q.front();

}

//cout << now.dep << endl;

vis[q.front()] = true;

q.pop();

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

if (vis[now.to[i]]) {

continue;

}

node[now.to[i]].dep = now.dep+1;

q.push(now.to[i]);

}

if (meta) {

return last;

}

return res;

}

int main(int argc, char *argv[]) {

int casecnt;

cin >> casecnt;

while (casecnt--) {

int n = 0,m = 0;

cin >> n >> m;

init_nodes(n,true);

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

int a = 0,b = 0;

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

node[a].to.push_back(b);

node[b].to.push_back(a);

}

int seed = (rand()%n)+1;

int meta = bfs(n,seed,true);

int diam = bfs(n, meta,false);

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

int k;

scanf(" %d",&k);

if (k <= diam) {

printf("%dn",k-1);

}else{

printf("%dn",diam-1+2*(k-diam));

}

return 0;

}

树的直径就是最长路，求法其实很简单的，就是两遍dfs，第一遍dfs把终点的节点编号输出来，第二次用这个节点当成起点再来一遍，这回输出最高深度，就是直径。

这个直径用法就是，如果需要过的节点数少于直径长度，说明不用拐弯，沿着直径走就ok，如果需要过的节点数大于直径长度，说明要拐弯，拐弯进去还要再出来，相当于走了两遍，所以是直径长度加上二倍多出来的分支长度，调整一下就ok了。

Asia – Tokyo – 2007/2008 UVa 3887 Slim Span

January 19, 20152015-01-19hahaschoolLeave 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>

using namespace std;

struct requestType{
    int a;
    int b;
    int cost;
};
vector<requestType> req;

int parent_bcj[105];

void init_bcj(){
    for (int i = 0; i < 105; i++) {
        parent_bcj[i] = i;
    }
}

int query_bcj(int currNode){
    if (parent_bcj[currNode] == currNode) {
        return currNode;
    }else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);
}

void unify_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == a) {
        parent_bcj[pa] = pb;
    }else {
        parent_bcj[pb] = pa;
    }

}

bool check_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == pb) {
        return true;
    }else{
        return false;
    }
}

bool cmp(requestType a,requestType b){
    return a.cost > b.cost;
}

int kruskal(int startReqPos,int n){
    init_bcj();
    int maxw = -1,minw = 10001,cnt = 0;
    for (int i = startReqPos; i < (int)req.size(); i++) {
        if (check_bcj(req[i].a, req[i].b)) {
            continue;
        }else{
            unify_bcj(req[i].a, req[i].b);
            maxw = max(req[i].cost,maxw);
            minw = min(req[i].cost,minw);
            cnt++;
        }
    }
    //cout << "+" << maxw-minw  << "=" << cnt << endl;
    if (cnt == n-1) {
        return maxw - minw;
    }else{
        return -1;
    }
}

int main(){
    int n = 0,m = 0;
    while (cin >> n >> m) {
        req.clear();
        if (n == 0 && m == 0) {
            break;
        }
        for (int i = 0;  i < m; i++) {
            requestType tmp;
            scanf(" %d %d %d",&tmp.a,&tmp.b,&tmp.cost);
            req.push_back(tmp);
        }
        sort(req.begin(), req.end(), cmp);
        int ans = 10001;
        for (int i = 0;i < (int)req.size(); i++) {
            int res = kruskal(i, n);
            if (res >= 0) {
                ans = min(ans, res);
            }
        }
        if (ans == 10001) {
            ans = -1;
        }
        cout << ans << endl;

    }


    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

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

using namespace std;

struct requestType{

int a;

int b;

int cost;

};

vector<requestType> req;

int parent_bcj[105];

void init_bcj(){

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

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

}else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost > b.cost;

}

int kruskal(int startReqPos,int n){

init_bcj();

int maxw = -1,minw = 10001,cnt = 0;

for (int i = startReqPos; i < (int)req.size(); i++) {

if (check_bcj(req[i].a, req[i].b)) {

continue;

}else{

unify_bcj(req[i].a, req[i].b);

maxw = max(req[i].cost,maxw);

minw = min(req[i].cost,minw);

cnt++;

}

//cout << "+" << maxw-minw << "=" << cnt << endl;

if (cnt == n-1) {

return maxw - minw;

}else{

return -1;

}

int main(){

int n = 0,m = 0;

while (cin >> n >> m) {

req.clear();

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

break;

}

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

requestType tmp;

scanf(" %d %d %d",&tmp.a,&tmp.b,&tmp.cost);

req.push_back(tmp);

}

sort(req.begin(), req.end(), cmp);

int ans = 10001;

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

int res = kruskal(i, n);

if (res >= 0) {

ans = min(ans, res);

}

if (ans == 10001) {

ans = -1;

}

cout << ans << endl;

}

return 0;

}

在kruskal的基础上，每一次干掉一条边，再kruskal一次，如果得到了生成树，就看看他的最大边权－最小边权是不是可以更新当前最优解，然后反复这么搞把所有边都搞掉就完成遍历了，因为事先已经对边权排序了，这么做并不会丢解。

POJ 1679 The Unique MST

January 19, 20152015-01-19hahaschoolLeave 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>

using namespace std;

struct requestType{
    int a;
    int b;
    double cost;
    bool flag;
    bool same;
};
vector<requestType> req;

int parent_bcj[105];

void init_bcj(){
    for (int i = 0; i < 105; i++) {
        parent_bcj[i] = i;
    }
}

int query_bcj(int currNode){
    if (parent_bcj[currNode] == currNode) {
        return currNode;
    }else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);
}

void unify_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == a) {
        parent_bcj[pa] = pb;
    }else {
        parent_bcj[pb] = pa;
    }

}

bool check_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == pb) {
        return true;
    }else{
        return false;
    }
}

bool cmp(requestType a,requestType b){
    return a.cost < b.cost;
}
bool reqToDel[1000005];
int kruskal(bool eliminate = false,bool firstTimeRun = true){
    //cout << "+" << eliminate <<  firstTimeRun << "+" << endl;
    init_bcj();
    int res = 0;
    for (int i = 0; i < req.size(); i++) {
        if (eliminate && reqToDel[i]) {
            continue;
        }
        if (check_bcj(req[i].a, req[i].b)) {
            continue;
        }else{
            if (firstTimeRun) {
                req[i].flag = true;
            }
            unify_bcj(req[i].a, req[i].b);
            res += req[i].cost;
        }
    }
    return res;
}

int main(int argc, char *argv[]) {
    int casecnt = 0;
    scanf(" %d",&casecnt);
    while (casecnt--) {
        int n = 0,m = 0;
        scanf(" %d %d",&n,&m);
        req.clear();
        memset(reqToDel, 0, sizeof(reqToDel));
        for (int i = 0;i < m; i++) {
            int a = 0,b = 0,c = 0;
            scanf(" %d %d %d",&a,&b,&c);
            requestType tmp;
            tmp.a = a,tmp.b = b,tmp.cost = c,tmp.flag = false,tmp.same = false;
            req.push_back(tmp);
        }
        sort(req.begin(), req.end(), cmp);
        for (int i = 0; i < m-1; i++) {
            if (req[i].cost == req[i+1].cost) {
                req[i].same = true;
                req[i+1].same = true;
            }
        }
        int initRes = kruskal();
        bool flag = true;
        for (int i = 0; i < req.size(); i++) {
            if (req[i].flag && req[i].same) {
                reqToDel[i] = true;
                if (kruskal(true,false) == initRes) {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) {
            cout << initRes << endl;
        }else{
            cout << "Not Unique!" << 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

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

using namespace std;

struct requestType{

int a;

int b;

double cost;

bool flag;

bool same;

};

vector<requestType> req;

int parent_bcj[105];

void init_bcj(){

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

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

}else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

bool reqToDel[1000005];

int kruskal(bool eliminate = false,bool firstTimeRun = true){

//cout << "+" << eliminate << firstTimeRun << "+" << endl;

init_bcj();

int res = 0;

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

if (eliminate && reqToDel[i]) {

continue;

}

if (check_bcj(req[i].a, req[i].b)) {

continue;

}else{

if (firstTimeRun) {

req[i].flag = true;

}

unify_bcj(req[i].a, req[i].b);

res += req[i].cost;

}

return res;

}

int main(int argc, char *argv[]) {

int casecnt = 0;

scanf(" %d",&casecnt);

while (casecnt--) {

int n = 0,m = 0;

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

req.clear();

memset(reqToDel, 0, sizeof(reqToDel));

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

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

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

requestType tmp;

tmp.a = a,tmp.b = b,tmp.cost = c,tmp.flag = false,tmp.same = false;

req.push_back(tmp);

}

sort(req.begin(), req.end(), cmp);

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

if (req[i].cost == req[i+1].cost) {

req[i].same = true;

req[i+1].same = true;

}

int initRes = kruskal();

bool flag = true;

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

if (req[i].flag && req[i].same) {

reqToDel[i] = true;

if (kruskal(true,false) == initRes) {

flag = false;

break;

}

if (flag) {

cout << initRes << endl;

}else{

cout << "Not Unique!" << endl;

}

return 0;

}

这个题我没想出来，一种解法是首先对于每条边确认是不是还有和这条边权值相同的其他边，如果有的话标记上，然后先来一遍裸的kruskal，把第一遍kruskal用到的节点全都标记上，然后开始扫，如果当前边既有同权的其他边又被在第一次kruskal中使用了了，就把这个边干掉再来一遍kruskal，看看这次生成树的总权值变没变，如果没有变就说明生成树不唯一，如果变了，就保持着这个边被干掉的状态接着扫，碰见符合要求的再干掉（保持着以前干掉的边被干掉的状态，用剩下的边尝试组生成树.如果你不判断有没有同权的边直接挨个把第一遍用过的边干掉，也可以。

RE了好多次然后换个编译器就过了，我也不知道是我抽了还是oj抽了，还有可能是.size()这个函数因为是返回unsigned long如果－1的话可能故障，以后要么强制类型转换，要么开个常数存一下。

POJ 1751 Highways

January 19, 20152015-01-19hahaschoolLeave 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>

using namespace std;

struct nodeType{
    double x;
    double y;
} node[755];

struct requestType{
    int a;
    int b;
    double cost;
};
vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){
    for (int i = 0; i < 1005; i++) {
        parent_bcj[i] = i;
    }
}

int query_bcj(int currNode){
    if (parent_bcj[currNode] == currNode) {
        return currNode;
    }else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);
}

void unify_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == a) {
        parent_bcj[pa] = pb;
    }else {
        parent_bcj[pb] = pa;
    }

}

bool check_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == pb) {
        return true;
    }else{
        return false;
    }
}

bool cmp(requestType a,requestType b){
    return a.cost < b.cost;
}

int main(){
    init_bcj();
    req.clear();
    memset(node, 0, sizeof(node));
    int n = 0;
    scanf(" %d",&n);
    for (int i = 1; i <= n; i++) {
        nodeType &now = node[i];
        scanf(" %lf %lf",&now.x,&now.y);
    }
    for (int i = 1;i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            requestType tmp;
            tmp.a = i,tmp.b = j,tmp.cost = sqrt(abs(node[i].x-node[j].x)*abs(node[i].x-node[j].x)+abs(node[i].y-node[j].y)*abs(node[i].y-node[j].y));
            req.push_back(tmp);
        }
    }
    int m;
    scanf(" %d",&m);
    for (int i = 1;i <= m; i++) {
        requestType tmp;
        int a,b;
        scanf(" %d %d",&a,&b);
        tmp.a = a,tmp.b = b,tmp.cost = 0;
        req.push_back(tmp);
    }
    sort(req.begin(), req.end(), cmp);
    for (int i =0; i < req.size(); i++) {
        if (check_bcj(req[i].a, req[i].b)) {
            continue;
        }{
            unify_bcj(req[i].a, req[i].b);
            if (req[i].cost) {
                printf("%d %dn",req[i].a,req[i].b);
            }
        }
    }

    return 0;
}

100

101

102

103

104

105

106

107

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

using namespace std;

struct nodeType{

double x;

double y;

} node[755];

struct requestType{

int a;

int b;

double cost;

};

vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){

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

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

}else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

int main(){

init_bcj();

req.clear();

memset(node, 0, sizeof(node));

int n = 0;

scanf(" %d",&n);

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

nodeType &now = node[i];

scanf(" %lf %lf",&now.x,&now.y);

}

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

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

requestType tmp;

tmp.a = i,tmp.b = j,tmp.cost = sqrt(abs(node[i].x-node[j].x)*abs(node[i].x-node[j].x)+abs(node[i].y-node[j].y)*abs(node[i].y-node[j].y));

req.push_back(tmp);

}

int m;

scanf(" %d",&m);

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

requestType tmp;

int a,b;

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

tmp.a = a,tmp.b = b,tmp.cost = 0;

req.push_back(tmp);

}

sort(req.begin(), req.end(), cmp);

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

if (check_bcj(req[i].a, req[i].b)) {

continue;

}{

unify_bcj(req[i].a, req[i].b);

if (req[i].cost) {

printf("%d %dn",req[i].a,req[i].b);

}

return 0;

}

要是在POJ上做的话不要交C++会T，交G＋＋就好了。

kruskal，没啥好说的。

HDU 1233 还是畅通工程

January 19, 20152015-01-19hahaschoolLeave 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>

using namespace std;

struct requestType{
    int a;
    int b;
    int cost;
};
vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){
    for (int i = 0; i < 1005; i++) {
        parent_bcj[i] = i;
    }
}

int query_bcj(int currNode){
    if (parent_bcj[currNode] == currNode) {
        return currNode;
    }else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);
}

void unify_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == a) {
        parent_bcj[pa] = pb;
    }else {
        parent_bcj[pb] = pa;
    }

}

bool check_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == pb) {
        return true;
    }else{
        return false;
    }
}

bool cmp(requestType a,requestType b){
    return a.cost < b.cost;
}

int main(){
    int n= 0;
    while (cin >> n && n) {
        init_bcj();
        req.clear();
        for (int i = 1; i <= n*(n-1)/2; i++) {
            int a,b,c;
            scanf(" %d %d %d",&a,&b,&c);
            requestType tmp;
            tmp.a = a,tmp.b = b,tmp.cost = c;
            req.push_back(tmp);
        }
        sort(req.begin(), req.end(), cmp);
        int res = 0;
        for (int i = 0; i < req.size(); i++) {
            requestType &now = req[i];
            if (check_bcj(now.a, now.b)) {
                continue;
            }else{
                res += now.cost;
                unify_bcj(now.a, now.b);
            }
        }
        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>

using namespace std;

struct requestType{

int a;

int b;

int cost;

};

vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){

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

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

}else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

int main(){

int n= 0;

while (cin >> n && n) {

init_bcj();

req.clear();

for (int i = 1; i <= n*(n-1)/2; i++) {

int a,b,c;

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

requestType tmp;

tmp.a = a,tmp.b = b,tmp.cost = c;

req.push_back(tmp);

}

sort(req.begin(), req.end(), cmp);

int res = 0;

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

requestType &now = req[i];

if (check_bcj(now.a, now.b)) {

continue;

}else{

res += now.cost;

unify_bcj(now.a, now.b);

}

cout << res << endl;

}

return 0;

}

拿1232的代码改一下就好了。

HDU 1232 畅通工程

January 19, 20152015-01-19hahaschoolLeave 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>

using namespace std;

struct requestType{
    int a;
    int b;
    int cost;
};
vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){
    for (int i = 0; i < 1005; i++) {
        parent_bcj[i] = i;
    }
}

int query_bcj(int currNode){
    if (parent_bcj[currNode] == currNode) {
        return currNode;
    }else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);
}

void unify_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == a) {
        parent_bcj[pa] = pb;
    }else {
        parent_bcj[pb] = pa;
    }

}

bool check_bcj(int a,int b){
    int pa = query_bcj(a);
    int pb = query_bcj(b);
    if (pa == pb) {
        return true;
    }else{
        return false;
    }
}

bool cmp(requestType a,requestType b){
    return a.cost < b.cost;
}

int main(){
    int n= 0,m = 0;
    while (cin >> n && n) {
        cin >> m;
        init_bcj();
        req.clear();
        for (int i = 1; i <= m; i++) {
            int a,b;
            scanf(" %d %d",&a,&b);
            requestType tmp;
            tmp.a = a,tmp.b = b,tmp.cost = 1;
            req.push_back(tmp);
        }
        sort(req.begin(), req.end(), cmp);
        int res = n-1;
        for (int i = 0; i < req.size(); i++) {
            requestType &now = req[i];
            if (check_bcj(now.a, now.b)) {
                continue;
            }else{
                res -= now.cost;
                unify_bcj(now.a, now.b);
            }
        }
        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>

using namespace std;

struct requestType{

int a;

int b;

int cost;

};

vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){

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

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

}else return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

int main(){

int n= 0,m = 0;

while (cin >> n && n) {

cin >> m;

init_bcj();

req.clear();

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

int a,b;

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

requestType tmp;

tmp.a = a,tmp.b = b,tmp.cost = 1;

req.push_back(tmp);

}

sort(req.begin(), req.end(), cmp);

int res = n-1;

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

requestType &now = req[i];

if (check_bcj(now.a, now.b)) {

continue;

}else{

res -= now.cost;

unify_bcj(now.a, now.b);

}

cout << res << endl;

}

return 0;

}

Kruskal算法，并查集老写挫，正确的写法是合并操作是把parentA和parentB合并（链接根节点），查询的时候压缩，就是

return parent_bcj[currNode] = query_bcj(parent_bcj[currNode]);

这句。

求有向图强连通分量的Tarjan算法

January 18, 20152015-01-18hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

vector<int> ljb[10005];
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;
    }
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

using namespace std;

vector<int> ljb[10005];

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;

}

-_-#上面的ccs应该是scc，名字叫错了跪。。。

关于Tarjan，https://www.byvoid.com/blog/scc-tarjan这个讲的挺好，一定要看看。然后我说下我自己咋想的。

首先初始化，对于每个节点都要分配一个dfn值和low值，开一个tim当作计时器，然后基本的流程就是：

～进入当前节点
～tim＋＋
～当前节点dfn＝low＝tim
～标记当前结点已经走过（注意图的遍历中节点只会走一次，也就是说标记不用撤销）
～把当前节点压入栈中（这个stack预先开好了）
～开始扫当前节点的分支，如果这个分支走过了，判断一下是不是这个分支是不是在栈里，如果在栈里的话就看看分支的dfn是不是比当前节点的low还小，小的话就把当前的low值调成那个dfn值；如果分支没走过，直接递归进到那个分支里去，等到递归出来之后，如果分支的low值比当前low值小，就令当前low值为分支low值（这步比较难懂）
～等到所有分支扫完，检查一下当前的dfn是不是等于low，如果不相等直接退出当前递归就好；相等的话，说明节点是scc的根，这个时候不断弹出栈，直到当前节点也被弹出，弹出的这些节点放在一起就是一组scc。

其实这个Tarjan的原理就是利用时间标记，进入栈的节点都是预定互相连通的，dfu值的意思就是当遍历到这个节点，是第几步（我把tim当作步来看），low的意思就是从当前节点可以走到的尽量在时间上先走到的栈内节点对应的dfu，就是最优解的对应标号，这个low肯定是越小越好，因为low越小我们的连通回路就越大。如果low＝dfu，那就是当前个点已经没有办法和栈里的既有的点连通了，所以当尝试了全部的走法之后还是没有找到一个栈里的节点来和当前点连通，就说明这个连通回路闭合了，这个时候只要把整个连通回路统统从栈里弹出来，就能得到整个连通回路，也就是scc的一个。每步中接下来要走的节点有三种情况：有的节点访问过但是不在栈里，这样的点不用考虑，因为它已经被弹出了，相当于这个节点已经和我们没关系了；有的点访问过而且在栈里，这样的节点有可能就是当前连通回路的终点了，所以我们要比较一下当前low值是不是比它的dfu大，如果大的话说明这个点可以连通过去，如果小的话说明我们已经有一种连通方式可以包括和它连通了，这个不是最优解，我们就忽略好了；有的节点没访问过，这样的点我们要递归进去处理一下，递归完之后这个节点就有了它在当前情形下该有的dfu和low了，因为这个点和当前点连通，所以这个点要是有一个比当前更好的连通方案，我们用它的就好。

基本就是这么搞，这种时间流逝标记的方法很重要（虽然我还不知道到底有多重要。。。）。