hahaschool

POJ 3258 River Hopscotch

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 l = 0,n = 0,m = 0;
    vector<int> rock;
    while (cin >> l >> n >> m) {
        for (int i = 1; i <= n; i++) {
            int tmp;
            scanf(" %d",&tmp);
            rock.push_back(tmp);
        }
        rock.push_back(l);
        rock.push_back(0);
        sort(rock.begin(), rock.end());

        int high = l,low = 0,mid = l/2;
        int ans = 0;
        while (high >= low) {
            mid = (high+low)/2;
            int cnt = 0,prev = 0;
            for (int i = 1; i < rock.size(); i++) {
                if (rock[i] - rock[prev] < mid) {
                    cnt++;
                }else {
                    prev = i;
                }
            }

            if (cnt > m) {
                high = mid-1;
            }else{
                ans = mid;
                low = mid+1;
            }
        }
        cout << ans << 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 l = 0,n = 0,m = 0;

vector<int> rock;

while (cin >> l >> n >> m) {

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

int tmp;

scanf(" %d",&tmp);

rock.push_back(tmp);

}

rock.push_back(l);

rock.push_back(0);

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

int high = l,low = 0,mid = l/2;

int ans = 0;

while (high >= low) {

mid = (high+low)/2;

int cnt = 0,prev = 0;

for (int i = 1; i < rock.size(); i++) {

if (rock[i] - rock[prev] < mid) {

cnt++;

}else {

prev = i;

}

if (cnt > m) {

high = mid-1;

}else{

ans = mid;

low = mid+1;

}

cout << ans << endl;

}

return 0;

}

二分不会啊。。。

POJ 2299 Ultra-QuickSort

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 INFINITE 1000000005

long long swapt = 0;
void merge(int* a,int start,int mid,int end){
    long long swaptimes = 0;
    vector<int> larr,rarr;
    for (int i = start; i <= mid; i++) {
        larr.push_back(a[i]);
    }
    larr.push_back(INFINITE);
    for (int i = mid+1; i <= end; i++) {
        rarr.push_back(a[i]);
    }
    rarr.push_back(INFINITE);
    int lcur = 0,rcur = 0;
    for (int cur = start; cur <= end; cur++) {
        if (larr[lcur] < rarr[rcur]) {
            a[cur] = larr[lcur];
            swaptimes += abs(lcur - cur + start);
            lcur++;
            continue;
        }else{
            a[cur] = rarr[rcur];
            swaptimes += abs(rcur + mid + 1 - cur);
            rcur++;
            continue;
        }
    }
    swapt += swaptimes/2;
}
void mergesrt(int* a,int start,int end){
    int mid = (start+end)/2;
    if (start < end) {
        mergesrt(a, start, mid);
        mergesrt(a, mid+1, end);
        merge(a,start,mid,end);
    }
}

int main(){
    int n = 0;
    int seq[500005];
    while (cin >> n && n) {
        swapt = 0;
        for (int i = 0; i < n; i++) {
            scanf(" %d",&seq[i]);
        }
        mergesrt(seq, 0, n-1);
        cout << swapt << 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 INFINITE 1000000005

long long swapt = 0;

void merge(int* a,int start,int mid,int end){

long long swaptimes = 0;

vector<int> larr,rarr;

for (int i = start; i <= mid; i++) {

larr.push_back(a[i]);

}

larr.push_back(INFINITE);

for (int i = mid+1; i <= end; i++) {

rarr.push_back(a[i]);

}

rarr.push_back(INFINITE);

int lcur = 0,rcur = 0;

for (int cur = start; cur <= end; cur++) {

if (larr[lcur] < rarr[rcur]) {

a[cur] = larr[lcur];

swaptimes += abs(lcur - cur + start);

lcur++;

continue;

}else{

a[cur] = rarr[rcur];

swaptimes += abs(rcur + mid + 1 - cur);

rcur++;

continue;

}

swapt += swaptimes/2;

}

void mergesrt(int* a,int start,int end){

int mid = (start+end)/2;

if (start < end) {

mergesrt(a, start, mid);

mergesrt(a, mid+1, end);

merge(a,start,mid,end);

}

int main(){

int n = 0;

int seq[500005];

while (cin >> n && n) {

swapt = 0;

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

scanf(" %d",&seq[i]);

}

mergesrt(seq, 0, n-1);

cout << swapt << endl;

}

return 0;

}

SXBK,总的交换次数会爆掉int。。。我他妈wa了一天

改造归并排序，保存交换次数就可以了

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

就这样。

POJ 3518 Prime Gap

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 1300000

bool prime[MAXN];

bool isPrime(int n){
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

void genPrime(){
    memset(prime, true, sizeof(prime));
    for (int i = 2; i < MAXN; i++) {
        if (prime[i]) {
            if (isPrime(i)) {
                for (int k = 2; k * i < MAXN; k++) {
                    prime[k*i] = false;
                }
            }else{
                prime[i] = false;
                continue;
            }
        }else{
            continue;
        }
    }
}


int main(){
    genPrime();
    int toQuery;
    while (cin >> toQuery) {
        if (!toQuery) {
            break;
        }
        int lbound = 0,rbound = 0;
        for (int i = toQuery; i >= 2; i--) {
            if (prime[i]) {
                lbound = i;
                break;
            }
        }
        for (int i = toQuery; i < MAXN; i++) {
            if (prime[i]) {
                rbound = i;
                break;
            }
        }
        cout << rbound - lbound << 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 1300000

bool prime[MAXN];

bool isPrime(int n){

for (int i = 2; i <= sqrt(n); i++) {

if (n % i == 0) {

return false;

}

return true;

}

void genPrime(){

memset(prime, true, sizeof(prime));

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

if (prime[i]) {

if (isPrime(i)) {

for (int k = 2; k * i < MAXN; k++) {

prime[k*i] = false;

}

}else{

prime[i] = false;

continue;

}

}else{

continue;

}

int main(){

genPrime();

int toQuery;

while (cin >> toQuery) {

if (!toQuery) {

break;

}

int lbound = 0,rbound = 0;

for (int i = toQuery; i >= 2; i--) {

if (prime[i]) {

lbound = i;

break;

}

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

if (prime[i]) {

rbound = i;

break;

}

cout << rbound - lbound << endl;

}

return 0;

}

埃氏筛法，没啥好说的嗯。

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;

}

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

POJ 2503 Babelfish

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;

map<string,string> dict;

int main(){
    ios_base::sync_with_stdio(false);
    string toProc;
    while (getline(cin,toProc) && toProc.size()) {
        string eng,dia;
        int i = 0;
        for (; i < toProc.size(); i++) {
            if (toProc[i] == ' ') {
                i++;
                break;
            }
            eng += toProc[i];
        }
        for (; i < toProc.size(); i++) {
            dia += toProc[i];
        }
        dict[dia] = eng;
    }
    while (cin >> toProc) {
        string toOut = dict[toProc];
        if (toOut.size()) {
            cout << toOut << endl;
        }else{
            cout << "eh" << 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;

map<string,string> dict;

int main(){

ios_base::sync_with_stdio(false);

string toProc;

while (getline(cin,toProc) && toProc.size()) {

string eng,dia;

int i = 0;

for (; i < toProc.size(); i++) {

if (toProc[i] == ' ') {

i++;

break;

}

eng += toProc[i];

}

for (; i < toProc.size(); i++) {

dia += toProc[i];

}

dict[dia] = eng;

}

while (cin >> toProc) {

string toOut = dict[toProc];

if (toOut.size()) {

cout << toOut << endl;

}else{

cout << "eh" << endl;

}

return 0;

}

这个是拿map水过去的版本，其实应该自己手写一个的。。。

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的话可能故障，以后要么强制类型转换，要么开个常数存一下。