HDU – Page 4 – hahaschool

HDU 1556 Color the ball

January 21, 20152015-01-21hahaschoolLeave 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 <map>
#include <stack>

using namespace std;

#define MAXN 262146

int tree[MAXN];
int M = 1;

void tree_init(int num){
    memset(tree, 0, sizeof(tree));
    M = 1;
    for (; M <= num; M <<= 1);
    M--;

}

void tree_add(int from,int to,int curl,int curr,unsigned int cur){
    //put cur = 1  curl = 1 curr = M+1 to initalize
    if (from <= curl && to >= curr) {
        //completely include T
        tree[cur]++;
        return;
    }else if(curl > to || curr < from){
        //completely out F0
        return;
    }else{
        //partially in F1
        cur <<= 1;
        tree_add(from, to, curl, (curl+curr)/2, cur);
        tree_add(from, to, (curl+curr)/2+1, curr, cur+1);
    }
}

int tree_query(unsigned int currNode){
    int res = 0;
    currNode += M;
    while (currNode) {
        res += tree[currNode];
        currNode >>= 1;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    int num = 0;
    while (cin >> num && num) {
        int n = num;
        tree_init(num);
        while (num--) {
            int a = 0,b = 0;
            cin >> a >> b;
            tree_add(min(a,b), max(a,b), 1, M+1, 1);
        }
        for (int i = 1; i <= n; i++) {
            cout << tree_query(i);
            if (i != n) {
                cout << ' ';
            }
        }
        cout << '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 <map>

#include <stack>

using namespace std;

#define MAXN 262146

int tree[MAXN];

int M = 1;

void tree_init(int num){

memset(tree, 0, sizeof(tree));

M = 1;

for (; M <= num; M <<= 1);

M--;

}

void tree_add(int from,int to,int curl,int curr,unsigned int cur){

//put cur = 1 curl = 1 curr = M+1 to initalize

if (from <= curl && to >= curr) {

//completely include T

tree[cur]++;

return;

}else if(curl > to || curr < from){

//completely out F0

return;

}else{

//partially in F1

cur <<= 1;

tree_add(from, to, curl, (curl+curr)/2, cur);

tree_add(from, to, (curl+curr)/2+1, curr, cur+1);

}

int tree_query(unsigned int currNode){

int res = 0;

currNode += M;

while (currNode) {

res += tree[currNode];

currNode >>= 1;

}

return res;

}

int main(){

ios_base::sync_with_stdio(false);

int num = 0;

while (cin >> num && num) {

int n = num;

tree_init(num);

while (num--) {

int a = 0,b = 0;

cin >> a >> b;

tree_add(min(a,b), max(a,b), 1, M+1, 1);

}

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

cout << tree_query(i);

if (i != n) {

cout << ' ';

}

cout << 'n';

}

return 0;

}

基于zkw线段树自己改造了一个，其实可以爆过去，时间还更少，真是邪乎。

HDU 1754 I Hate It

January 21, 20152015-01-21hahaschoolLeave 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 <map>
#include <stack>

using namespace std;

#define MAXN 1048576

int tree[MAXN];
int M = 1;

void tree_init(int num){
    memset(tree, 0, sizeof(tree));
    M = 1;
    for (; M <= num; M <<= 1);
    M <<= 1;
    M--;
}

int tree_query(unsigned int from,unsigned int to){
    from--,to++;
    from += M,to += M;
    int res = 0;
    while (from^to^1) {
        //cout << "+" << from << "+" << to << '~' << endl;
        if (~from & 1) {//这里是按位取反，不是负号，也不能和0与那样的话肯定是0啊
            //from on left
            res = max(res,tree[from+1]);
        }
        if (to & 1) {
            //to on right
            res = max(res,tree[to-1]);
        }
        from >>= 1,to >>= 1;
    }
    return res;
}

void tree_update(unsigned int nodeNum,int newGrade){
    nodeNum += M;
    tree[nodeNum] = newGrade;
    while (nodeNum != 1) {
        nodeNum >>= 1;
        tree[nodeNum] = max(tree[nodeNum << 1],tree[(nodeNum << 1) + 1]);
    }
}


int main(){
    int n = 0,m = 0;
    while (cin >> n >> m) {
        tree_init(n);
        for (int i = 1; i <= n; i++) {
            int arg;
            scanf(" %d",&arg);
            tree_update(i+1, arg);
        }
        for (int i = 1; i <= m; i++) {
            char cmd;
            int arg1 = 0,arg2 = 0;
            scanf(" %c %d %d",&cmd,&arg1,&arg2);
            if (cmd == 'U') {
                arg1++;
                tree_update(arg1, arg2);
            }else{
                arg1++,arg2++;
                cout << tree_query(min(arg1,arg2), max(arg1,arg2)) << 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 <map>

#include <stack>

using namespace std;

#define MAXN 1048576

int tree[MAXN];

int M = 1;

void tree_init(int num){

memset(tree, 0, sizeof(tree));

M = 1;

for (; M <= num; M <<= 1);

M <<= 1;

M--;

}

int tree_query(unsigned int from,unsigned int to){

from--,to++;

from += M,to += M;

int res = 0;

while (from^to^1) {

//cout << "+" << from << "+" << to << '~' << endl;

if (~from & 1) {//这里是按位取反，不是负号，也不能和0与那样的话肯定是0啊

//from on left

res = max(res,tree[from+1]);

}

if (to & 1) {

//to on right

res = max(res,tree[to-1]);

}

from >>= 1,to >>= 1;

}

return res;

}

void tree_update(unsigned int nodeNum,int newGrade){

nodeNum += M;

tree[nodeNum] = newGrade;

while (nodeNum != 1) {

nodeNum >>= 1;

tree[nodeNum] = max(tree[nodeNum << 1],tree[(nodeNum << 1) + 1]);

}

int main(){

int n = 0,m = 0;

while (cin >> n >> m) {

tree_init(n);

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

int arg;

scanf(" %d",&arg);

tree_update(i+1, arg);

}

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

char cmd;

int arg1 = 0,arg2 = 0;

scanf(" %c %d %d",&cmd,&arg1,&arg2);

if (cmd == 'U') {

arg1++;

tree_update(arg1, arg2);

}else{

arg1++,arg2++;

cout << tree_query(min(arg1,arg2), max(arg1,arg2)) << endl;

}

return 0;

}

数组开的比较大，清数组会消耗很多时间所以跑了1000多。

基于zkw版线段树实现。

HDU 1540 Tunnel Warfare

January 20, 20152015-01-20hahaschoolLeave 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 <map>
#include <stack>

using namespace std;

#define MAXN 50005

bool ok[MAXN];

int main(){
    int n = 0,m = 0;
    while (cin >> n >> m) {
        stack<int> op;
        set<int> broken;
        memset(ok, true,sizeof(ok));
        broken.clear();
        while (!op.empty()) {
            op.pop();
        }
        ok[0] = false;
        for (int i = 1; i <= m; i++) {
            char cmd;
            int arg;
            scanf(" %c",&cmd);
            if (cmd == 'D') {
                scanf(" %d",&arg);
                op.push(arg);
                broken.insert(arg);
                ok[arg] = false;
            }else if(cmd == 'Q'){
                scanf(" %d",&arg);
                if (broken.size() == 0) {
                    cout << n << endl;
                    continue;
                }
                set<int>::iterator it = lower_bound(broken.begin(), broken.end(), arg);
                if (*it == arg) {
                    cout << 0 << endl;
                    continue;
                }else{
                    int l = 0,r = 0;
                    if (it != broken.end()) {
                        r = *it;
                        r--;
                    }else{
                        r = n;
                    }
                    if (it == broken.begin()) {
                        l = 0;
                    }else{
                        it--;
                        l = *it;
                    }
                    //cout << "+" << l << "+" << r << endl;
                    cout << r-l << endl;
                }
            }else{
                if (op.empty()) {
                    continue;
                }
                ok[op.top()] = true;
                broken.erase(broken.find(op.top()));
                op.pop();
            }
        }
    }

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

#include <stack>

using namespace std;

#define MAXN 50005

bool ok[MAXN];

int main(){

int n = 0,m = 0;

while (cin >> n >> m) {

stack<int> op;

set<int> broken;

memset(ok, true,sizeof(ok));

broken.clear();

while (!op.empty()) {

op.pop();

}

ok[0] = false;

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

char cmd;

int arg;

scanf(" %c",&cmd);

if (cmd == 'D') {

scanf(" %d",&arg);

op.push(arg);

broken.insert(arg);

ok[arg] = false;

}else if(cmd == 'Q'){

scanf(" %d",&arg);

if (broken.size() == 0) {

cout << n << endl;

continue;

}

set<int>::iterator it = lower_bound(broken.begin(), broken.end(), arg);

if (*it == arg) {

cout << 0 << endl;

continue;

}else{

int l = 0,r = 0;

if (it != broken.end()) {

r = *it;

r--;

}else{

r = n;

}

if (it == broken.begin()) {

l = 0;

}else{

it--;

l = *it;

}

//cout << "+" << l << "+" << r << endl;

cout << r-l << endl;

}

}else{

if (op.empty()) {

continue;

}

ok[op.top()] = true;

broken.erase(broken.find(op.top()));

op.pop();

}

return 0;

}

这个是用STL水过去的啊，可不是什么正规做法。

HDU 1969 Pie

January 20, 20152015-01-20hahaschoolLeave a comment

#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <vector>
#include <queue>
using namespace std;
bool cmp(int a,int b){
    return a>b;
}
int main(){
    int caseCnt = 0;
    scanf("%d",&caseCnt);
    for (int xxi = 1; xxi <= caseCnt; xxi++) {
        int n = 0,f= 0;
        double r[10005];
        cin >> n >> f;
        for (int i = 1; i <= n; i++) {
            scanf("%lf",&r[i-1]);
            r[i-1] *= r[i-1];
        }
        f++;
        sort(r, r+n, cmp);
        double high = r[0],low = 0;
        int rf;
        bool ans = false;
        double i = (high+low)/2;
        while (high - low > 0.0000001){
            ans = false;
            i = (high+low)/2;
            rf = f;
            for (int q = 1; q <= n; q++) {
                rf -= (int)(r[q-1]/i);
                if (rf <= 0) {
                    ans = true;
                    break;
                }
            }
            if (!ans) {
                high = i;
            }else{
                low = i;
            }
        }
        double pi = asin(1.0) * 2;
        printf("%.4lfn",i * pi);
    }
    return 0;
}

#include <cmath>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <string>

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <vector>

#include <queue>

using namespace std;

bool cmp(int a,int b){

return a>b;

}

int main(){

int caseCnt = 0;

scanf("%d",&caseCnt);

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

int n = 0,f= 0;

double r[10005];

cin >> n >> f;

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

scanf("%lf",&r[i-1]);

r[i-1] *= r[i-1];

}

f++;

sort(r, r+n, cmp);

double high = r[0],low = 0;

int rf;

bool ans = false;

double i = (high+low)/2;

while (high - low > 0.0000001){

ans = false;

i = (high+low)/2;

rf = f;

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

rf -= (int)(r[q-1]/i);

if (rf <= 0) {

ans = true;

break;

}

if (!ans) {

high = i;

}else{

low = i;

}

double pi = asin(1.0) * 2;

printf("%.4lfn",i * pi);

}

return 0;

}

二分的，然后要注意自已还得吃呢，别都给人家了，所以f要＋1，然后在hdu上，用long double一定wa，不用想，改成double就好了。

就这样。

HDU 1157 Who's in the Middle

January 20, 20152015-01-20hahaschoolLeave 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 <map>
#include <stack>

using namespace std;

int main(){
    int n = 0;
    while (cin >> n) {
        vector<int> cows;
        while (n--) {
            int k = 0;
            cin >> k;
            cows.push_back(k);
        }
        sort(cows.begin(),cows.end());
        cout << cows[(cows.size()-1)/2] << 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 <map>

#include <stack>

using namespace std;

int main(){

int n = 0;

while (cin >> n) {

vector<int> cows;

while (n--) {

int k = 0;

cin >> k;

cows.push_back(k);

}

sort(cows.begin(),cows.end());

cout << cows[(cows.size()-1)/2] << endl;

}

return 0;

}

我先给水过去，然后加难度。。。

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了。

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]);

这句。

HDU 1285 确定比赛名次

January 18, 20152015-01-18hahaschoolLeave 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 typeNode{
    int in;
    vector<int> from;
    vector<int> to;
} node[505];

vector<int> req;
vector<int> res;
int main(){
    int n = 0,m = 0;
    while (cin >> n >> m) {
        req.clear();
        res.clear();
        for (int i = 1; i <= n; i++) {
            node[i].to.clear();
            node[i].from.clear();
            node[i].in = 0;
        }
        for (int i = 1; i <= m; i++) {
            int a = 0,b = 0;
            cin >> b >> a;
            node[b].to.push_back(a);
            node[a].from.push_back(b);
            node[a].in++;
        }
        bool flag = true;
        while (flag) {
            flag = false;
            for (int i = 1; i <= n; i++) {
                if (node[i].in == 0) {
                    res.push_back(i);
                    node[i].in--;
                    flag = true;
                    for (int j = 0; j < node[i].to.size(); j++) {
                        node[node[i].to[j]].in--;
                    }
                    break;
                }
            }
        }
        for (int i = 0; i < res.size();i++) {
            cout << res[i];
            if (i != res.size()-1) {
                cout << " ";
            }
        }
        cout << 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 typeNode{

int in;

vector<int> from;

vector<int> to;

} node[505];

vector<int> req;

vector<int> res;

int main(){

int n = 0,m = 0;

while (cin >> n >> m) {

req.clear();

res.clear();

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

node[i].to.clear();

node[i].from.clear();

node[i].in = 0;

}

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

int a = 0,b = 0;

cin >> b >> a;

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

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

node[a].in++;

}

bool flag = true;

while (flag) {

flag = false;

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

if (node[i].in == 0) {

res.push_back(i);

node[i].in--;

flag = true;

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

node[node[i].to[j]].in--;

}

break;

}

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

cout << res[i];

if (i != res.size()-1) {

cout << " ";

}

cout << endl;

}

return 0;

}

拓扑排序相关，还不怎么会，绕了好多弯路，要好好学习总结下嗯-_-#

HDU 1710 Binary Tree Traversals

January 18, 20152015-01-18hahaschoolOne 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;

int dlr[1005],ldr[1005],cnt,vis[1005];
stack<int> lrd;

int finddlr(int target){
    for (int i = 0; i < cnt; i++) if (dlr[i] == target) return i;
    return 0;
}

int findldr(int target){
    for (int i = 0; i < cnt; i++) if (ldr[i] == target) return i;
    return -1;
}

int findlen(bool right,int pos){
    //true for right false for left
    if (right) {
        for (int i = pos+1; i < cnt; i++) if (vis[i]) return i-pos-1;
        return cnt-pos-1;
    }else{
        for (int i = pos-1; i >= 0;i--) if (vis[i]) return pos-i-1;
        return pos;
    }

}
void genlrd(int root){
    lrd.push(root);
    int a = finddlr(root);
    int b = findldr(root);
    vis[b] = true;
    int ltlen = findlen(false,b);
    int rtlen = findlen(true,b);
    int ltroot = dlr[a+1];
    int rtroot = dlr[a+ltlen+1];
    if (rtlen) genlrd(rtroot);
    if (ltlen) genlrd(ltroot);
}

int main(int argc, char *argv[]){
    while (cin >> cnt) {
        memset(dlr, 0, sizeof(dlr));
        memset(ldr, 0, sizeof(ldr));
        memset(vis, 0, sizeof(vis));
        while (!lrd.empty()) lrd.pop();
        for (int i = 0; i < cnt; i++) cin >> dlr[i];
        for (int i = 0; i < cnt; i++) cin >> ldr[i];
        genlrd(dlr[0]);
        while (!lrd.empty()) {
            cout << lrd.top();
            if (lrd.size() != 1) cout << " ";
            lrd.pop();
        }
        cout << 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;

int dlr[1005],ldr[1005],cnt,vis[1005];

stack<int> lrd;

int finddlr(int target){

for (int i = 0; i < cnt; i++) if (dlr[i] == target) return i;

return 0;

}

int findldr(int target){

for (int i = 0; i < cnt; i++) if (ldr[i] == target) return i;

return -1;

}

int findlen(bool right,int pos){

//true for right false for left

if (right) {

for (int i = pos+1; i < cnt; i++) if (vis[i]) return i-pos-1;

return cnt-pos-1;

}else{

for (int i = pos-1; i >= 0;i--) if (vis[i]) return pos-i-1;

return pos;

}

void genlrd(int root){

lrd.push(root);

int a = finddlr(root);

int b = findldr(root);

vis[b] = true;

int ltlen = findlen(false,b);

int rtlen = findlen(true,b);

int ltroot = dlr[a+1];

int rtroot = dlr[a+ltlen+1];

if (rtlen) genlrd(rtroot);

if (ltlen) genlrd(ltroot);

}

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

while (cin >> cnt) {

memset(dlr, 0, sizeof(dlr));

memset(ldr, 0, sizeof(ldr));

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

while (!lrd.empty()) lrd.pop();

for (int i = 0; i < cnt; i++) cin >> dlr[i];

for (int i = 0; i < cnt; i++) cin >> ldr[i];

genlrd(dlr[0]);

while (!lrd.empty()) {

cout << lrd.top();

if (lrd.size() != 1) cout << " ";

lrd.pop();

}

cout << endl;

}

return 0;

}

这道题是已知DLR和LDR，求LRD。

DLR（先序）具有的特点是根节点一定在它连接的子树的左边，子树的根节点一定在子树的子树的左边，LDR的特点是投影，就是下面这个图：

接下来就拿样例举例子：

这个的DLR是1 2 4 7 3 5 8 9 6
这个可以分段看，首先是 1/247/35869，然后可以发现1是root，247又可以分成2/47/～三段（～表示没有节点），在这里2是这个子树的根，35896又可以分为3/589/6在这里3是右边子树的根，589是左半部分，6是右半部分，就这样一直分下去就可以发现DLR的特点了，而这种特点正是因为DLR是DFS生成的。

然后看LDR，4 7 2 1 8 5 9 3 6
这个也是分段，首先472/1/85936，你会发现如果知道根的话，那么这个根左边有什么右边有什么都是可以从LDR里看出来的。

所以我们这个题就可以先找到总根（DLR第一位），然后在LDR里找到根的位置，想办法确定左右肢的元素个数，然后回到DLR里找到左右肢的根，分别把它们当作总根递归下去，这样我们就能还原出树的全貌了，而这个题更简单一点，你只要以DRL的顺序这么递归，把每一次找到的根都压入stack里，最后再逐个弹出输出，正好就是LRD了。

如果已知LRD和LDR，是可以求出DLR的，方法和这个差不太多。但是如果知道DLR喝LRD，想求LDR做不到，LDR不止一个解。