POJ – Page 4 – 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对应的终止情形，就是答案。

POJ 2828 Buy Tickets

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 <list>
#include <stack>

using namespace std;

#define MAXN 1100000

int tree[MAXN];
int M = 1;

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

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

void tree_build(int cnt){
    for (int i = 1; i <= cnt; i++) {
        tree[M+i] = 1;
    }
    int cur = M+1;
    while (cur >>= 1) {
        for (int i = 0; i < cur; i++) {
            tree[cur+i] = tree[cur << 1] + tree[(cur << 1) + 1];
        }
    }
}
int tree_insert(int arg,int cur){
    while (cur <= M) {
        int lch = tree[cur << 1];
        if (lch <= arg) {
            arg -= lch;
            cur <<= 1;
            cur++;
        }else{
            cur <<= 1;
        }
    }
        tree_update(cur-M, -1);
        return cur-M;
}
int que[200005],sarg1[200005],sarg2[200005];
int main(){
    int cnt;
    while (scanf(" %d",&cnt) != EOF) {
        tree_init(cnt);
        memset(que, 0, sizeof(int)*cnt+4);
        for (int i = 1; i <= cnt; i++) {
            scanf(" %d %d",&sarg1[i],&sarg2[i]);
        }
        tree_build(cnt);
        for (int i = cnt; i >= 1; i--){
            int arg1 = sarg1[i],arg2 = sarg2[i];
            que[tree_insert(arg1, 1)] = arg2;
        }
        for (int i = 1; i <= cnt; i++) {
            printf("%d",que[i]);
            if (i!=cnt) {
                printf(" ");
            }
        }
        printf("\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 <list>

#include <stack>

using namespace std;

#define MAXN 1100000

int tree[MAXN];

int M = 1;

void tree_init(int num){

M = 1;

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

memset(tree, 0, sizeof(int)*M*2+2);

M--;

}

void tree_update(unsigned int nodeNum,int delta){

nodeNum += M;

tree[nodeNum] += delta;

while (nodeNum != 1) {

nodeNum >>= 1;

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

}

void tree_build(int cnt){

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

tree[M+i] = 1;

}

int cur = M+1;

while (cur >>= 1) {

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

tree[cur+i] = tree[cur << 1] + tree[(cur << 1) + 1];

}

int tree_insert(int arg,int cur){

while (cur <= M) {

int lch = tree[cur << 1];

if (lch <= arg) {

arg -= lch;

cur <<= 1;

cur++;

}else{

cur <<= 1;

}

tree_update(cur-M, -1);

return cur-M;

}

int que[200005],sarg1[200005],sarg2[200005];

int main(){

int cnt;

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

tree_init(cnt);

memset(que, 0, sizeof(int)*cnt+4);

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

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

}

tree_build(cnt);

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

int arg1 = sarg1[i],arg2 = sarg2[i];

que[tree_insert(arg1, 1)] = arg2;

}

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

printf("%d",que[i]);

if (i!=cnt) {

printf(" ");

}

printf("\n");

}

return 0;

}

这个是灵活使用线段树了，把线段树当作路径，一边整理有多少个空位，一边按着这些数据快速地插入节点。

注意这个题正难则反的思想，反着来看这个请求序列，是可以做的，正着处理就坏事了，所以当卡题的时候不妨试一试把当前的思考／阅读方向反过来，也许会有灵感。

我已经很尽力地优化了，1600跑过，只能说那些几百跑过的大神真是强，无法比肩。

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了一天

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

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;

}

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

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水过去的版本，其实应该自己手写一个的。。。

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，没啥好说的。

POJ 1256 Anagram

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

using namespace std;


char chain[52] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};
bool cmp(char a,char b){
    if (a == b) {
        return false;
    }
    bool flag = false;
    for (int i = 0;i < 52;i++) {
        if (a == chain[i]) {
            flag = true;
            break;
        }
        if (b == chain[i]) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main(){
    int cnt;
    cin >> cnt;
    while (cnt--) {
        string toProc;
        cin >> toProc;
        while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

        }
        cout << toProc << endl;
        while (next_permutation(toProc.begin(), toProc.end(),cmp)) {
            cout << toProc << 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>

using namespace std;

char chain[52] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j','K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t','U','u','V','v','W','w','X','x','Y','y','Z','z'};

bool cmp(char a,char b){

if (a == b) {

return false;

}

bool flag = false;

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

if (a == chain[i]) {

flag = true;

break;

}

if (b == chain[i]) {

flag = false;

break;

}

return flag;

}

int main(){

int cnt;

cin >> cnt;

while (cnt--) {

string toProc;

cin >> toProc;

while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

}

cout << toProc << endl;

while (next_permutation(toProc.begin(), toProc.end(),cmp)) {

cout << toProc << endl;

}

return 0;

}

next_permutation的返回bool值的含义是接下来还有没有可以用的排列。

然后要注意这个题的排序方式是特殊的，要自己构建排序函数。

排序函数返回值的意思是：如果返回true，则交换两个值，返回false，则不对两个值操作，所以如果a＝＝b一定要返回false，否则会死循环。

POJ 1002 487-3279

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

using namespace std;

int tel[10000000];

int main(){
    int cnt = 0;
    cin >> cnt;
    while (cnt--) {
        char toProc[1000];
        scanf(" %s",toProc);
        int len = strlen(toProc);
        int pow = 1000000,telnum = 0;
        for (int i = 0; i < len; i++) {
            if (isdigit(toProc[i])) {
                //digit
                telnum += pow * (toProc[i] - '0');
                pow /= 10;
            }else if (isalpha(toProc[i])) {
                //alpha
                if (toProc[i] == 'Q' || toProc[i] == 'Z' ) {
                    continue;
                }
                if (toProc[i] == 'A' || toProc[i] == 'B' || toProc[i] == 'C') {
                    telnum += pow * 2;
                }
                if (toProc[i] == 'D' || toProc[i] == 'E' || toProc[i] == 'F') {
                    telnum += pow * 3;
                }
                if (toProc[i] == 'G' || toProc[i] == 'H' || toProc[i] == 'I') {
                    telnum += pow * 4;
                }
                if (toProc[i] == 'J' || toProc[i] == 'K' || toProc[i] == 'L') {
                    telnum += pow * 5;
                }
                if (toProc[i] == 'M' || toProc[i] == 'N' || toProc[i] == 'O') {
                    telnum += pow * 6;
                }
                if (toProc[i] == 'P' || toProc[i] == 'R' || toProc[i] == 'S') {
                    telnum += pow * 7;
                }
                if (toProc[i] == 'T' || toProc[i] == 'U' || toProc[i] == 'V') {
                    telnum += pow * 8;
                }
                if (toProc[i] == 'W' || toProc[i] == 'X' || toProc[i] == 'Y') {
                    telnum += pow * 9;
                }
                pow /= 10;
            }
        }
        tel[telnum]++;
        //cout << telnum << endl;
    }
    bool flag = false;
    for (int i = 0; i < 10000000; i++) {
        if (tel[i] > 1) {
            flag = true;
            int pow = 1000000;
            int tmp = i;
            while (pow) {
                if (pow == 1000) {
                    cout << '-';
                }
                cout << tmp/pow;
                tmp -= (tmp/pow) * pow;
                pow /= 10;
            }
            cout << ' ' << tel[i] << endl;
        }
    }
    if (!flag) {
        cout << "No duplicates." << 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>

using namespace std;

int tel[10000000];

int main(){

int cnt = 0;

cin >> cnt;

while (cnt--) {

char toProc[1000];

scanf(" %s",toProc);

int len = strlen(toProc);

int pow = 1000000,telnum = 0;

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

if (isdigit(toProc[i])) {

//digit

telnum += pow * (toProc[i] - '0');

pow /= 10;

}else if (isalpha(toProc[i])) {

//alpha

if (toProc[i] == 'Q' || toProc[i] == 'Z' ) {

continue;

}

if (toProc[i] == 'A' || toProc[i] == 'B' || toProc[i] == 'C') {

telnum += pow * 2;

}

if (toProc[i] == 'D' || toProc[i] == 'E' || toProc[i] == 'F') {

telnum += pow * 3;

}

if (toProc[i] == 'G' || toProc[i] == 'H' || toProc[i] == 'I') {

telnum += pow * 4;

}

if (toProc[i] == 'J' || toProc[i] == 'K' || toProc[i] == 'L') {

telnum += pow * 5;

}

if (toProc[i] == 'M' || toProc[i] == 'N' || toProc[i] == 'O') {

telnum += pow * 6;

}

if (toProc[i] == 'P' || toProc[i] == 'R' || toProc[i] == 'S') {

telnum += pow * 7;

}

if (toProc[i] == 'T' || toProc[i] == 'U' || toProc[i] == 'V') {

telnum += pow * 8;

}

if (toProc[i] == 'W' || toProc[i] == 'X' || toProc[i] == 'Y') {

telnum += pow * 9;

}

pow /= 10;

}

tel[telnum]++;

//cout << telnum << endl;

}

bool flag = false;

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

if (tel[i] > 1) {

flag = true;

int pow = 1000000;

int tmp = i;

while (pow) {

if (pow == 1000) {

cout << '-';

}

cout << tmp/pow;

tmp -= (tmp/pow) * pow;

pow /= 10;

}

cout << ' ' << tel[i] << endl;

}

if (!flag) {

cout << "No duplicates." << endl;

}

return 0;

}

真是良／心／题

首先要注意没有重复情形的时候，要输出一句话

然后以0开头的电话号码要处理

然后输入时候不能用cin

嗯就这样{(-_-)}