hahaschool

POJ 1751 Highways

January 19, 20152015-01-19hahaschoolLeave a comment

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

using namespace std;

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

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

int parent_bcj[1005];

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

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

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

}

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

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

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

    return 0;
}

100

101

102

103

104

105

106

107

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

using namespace std;

struct nodeType{

double x;

double y;

} node[755];

struct requestType{

int a;

int b;

double cost;

};

vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){

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

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

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

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

int main(){

init_bcj();

req.clear();

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

int n = 0;

scanf(" %d",&n);

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

nodeType &now = node[i];

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

}

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

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

requestType tmp;

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

req.push_back(tmp);

}

int m;

scanf(" %d",&m);

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

requestType tmp;

int a,b;

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

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

req.push_back(tmp);

}

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

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

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

continue;

}{

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

if (req[i].cost) {

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

}

return 0;

}

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

kruskal，没啥好说的。

HDU 1233 还是畅通工程

January 19, 20152015-01-19hahaschoolLeave a comment

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

using namespace std;

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

int parent_bcj[1005];

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

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

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

}

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

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

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

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

using namespace std;

struct requestType{

int a;

int b;

int cost;

};

vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){

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

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

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

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

int main(){

int n= 0;

while (cin >> n && n) {

init_bcj();

req.clear();

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

int a,b,c;

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

requestType tmp;

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

req.push_back(tmp);

}

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

int res = 0;

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

requestType &now = req[i];

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

continue;

}else{

res += now.cost;

unify_bcj(now.a, now.b);

}

cout << res << endl;

}

return 0;

}

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

HDU 1232 畅通工程

January 19, 20152015-01-19hahaschoolLeave a comment

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

using namespace std;

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

int parent_bcj[1005];

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

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

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

}

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

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

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

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

using namespace std;

struct requestType{

int a;

int b;

int cost;

};

vector<requestType> req;

int parent_bcj[1005];

void init_bcj(){

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

parent_bcj[i] = i;

}

int query_bcj(int currNode){

if (parent_bcj[currNode] == currNode) {

return currNode;

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

}

void unify_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == a) {

parent_bcj[pa] = pb;

}else {

parent_bcj[pb] = pa;

}

bool check_bcj(int a,int b){

int pa = query_bcj(a);

int pb = query_bcj(b);

if (pa == pb) {

return true;

}else{

return false;

}

bool cmp(requestType a,requestType b){

return a.cost < b.cost;

}

int main(){

int n= 0,m = 0;

while (cin >> n && n) {

cin >> m;

init_bcj();

req.clear();

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

int a,b;

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

requestType tmp;

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

req.push_back(tmp);

}

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

int res = n-1;

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

requestType &now = req[i];

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

continue;

}else{

res -= now.cost;

unify_bcj(now.a, now.b);

}

cout << res << endl;

}

return 0;

}

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

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

这句。

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不止一个解。

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

January 18, 20152015-01-18hahaschoolLeave a comment

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

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

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

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

using namespace std;

vector<int> ljb[10005];

bool vis[10005];

bool instk[10005];

int dfn[10005];

int low[10005];

int tim = 0;

stack<int> stk;

vector<vector<int> > ccs;

void dfs(int currNode){

vis[currNode] = true;

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

stk.push(currNode);

instk[currNode] = true;

vector<int> now = ljb[currNode];

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

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

dfs(now[i]);

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

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

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

}

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

int tmp = 0;

vector<int> res;

while (currNode != tmp) {

tmp = stk.top();

res.push_back(tmp);

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

stk.pop();

instk[tmp] = false;

}

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

ccs.push_back(res);

//cout << endl;

}

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

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

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

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

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

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

HDU 1269 迷宫城堡

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>


using namespace std;

vector<int> ljb[10005];
vector<int> ljbt[10005];
bool res[10005];

void dfs(bool t,int currNode){
	res[currNode] = true;
	vector<int> now;
	if(t) now = ljbt[currNode];
	else now = ljb[currNode];
	for (int i = 0;i < now.size();i++) {
		if (res[now[i]]) continue;
		dfs(t,now[i]);
	}
}

int main(){
	int n = 0,m = 0;
	while (scanf(" %d %d",&n,&m) != EOF) {
		if (n == 0 && m == 0){
			break;
		}else {
			for (int i = 1;i <= n;i++) {
				ljb[i].clear();
				ljbt[i].clear();
			}
			for (int i = 1;i <= m;i++) {
				int a = 0,b = 0;
				scanf(" %d %d",&a,&b);
				ljb[a].push_back(b);
				ljbt[b].push_back(a);
			}
			bool flag = true;
			memset(res,0,sizeof(res));
			dfs(true,1);
			for (int i = 1;i <= n;i++) {
				if(!res[i]){
					flag = false;
					break;
				}
			}
			if(flag){
				memset(res,0,sizeof(res));
				dfs(false,1);
				for (int i = 1;i <= n;i++) {
					if(!res[i]){
						flag = false;
						break;
					}
				}
			}
			if(flag){
				cout << "Yes" << endl;
			}else{
				cout << "No" << 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;

vector<int> ljb[10005];

vector<int> ljbt[10005];

bool res[10005];

void dfs(bool t,int currNode){

res[currNode] = true;

vector<int> now;

if(t) now = ljbt[currNode];

else now = ljb[currNode];

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

if (res[now[i]]) continue;

dfs(t,now[i]);

}

int main(){

int n = 0,m = 0;

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

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

break;

}else {

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

ljb[i].clear();

ljbt[i].clear();

}

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

int a = 0,b = 0;

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

ljb[a].push_back(b);

ljbt[b].push_back(a);

}

bool flag = true;

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

dfs(true,1);

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

if(!res[i]){

flag = false;

break;

}

if(flag){

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

dfs(false,1);

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

if(!res[i]){

flag = false;

break;

}

if(flag){

cout << "Yes" << endl;

}else{

cout << "No" << 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;

vector<int> ljb[10005];

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

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


int main(){
    int n = 0,m = 0;
    while (scanf(" %d %d",&n,&m) != EOF) {
        if (n == 0 && m == 0){
            break;
        }else {
            for (int i = 1;i <= n;i++) {
                ljb[i].clear();
            }
            for (int i = 1;i <= m;i++) {
                int a= 0,b = 0;
                scanf(" %d %d",&a,&b);
                ljb[a].push_back(b);
            }
            memset(vis, 0, sizeof(vis));
            memset(instk, 0, sizeof(instk));
            memset(dfn, 0, sizeof(dfn));
            memset(low, 0, sizeof(low));
            ccs.clear();
            while (!stk.empty()) {
                stk.pop();
            }
            dfs(1);
            bool flag = false;
            for (int i = 0; i < ccs.size(); i++) {
                if (ccs[i].size() == n) {
                    flag = true;
                }
            }
            if (flag) {
                cout << "Yes" << endl;
            }else {
                cout << "No" << 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;

vector<int> ljb[10005];

bool vis[10005];

bool instk[10005];

int dfn[10005];

int low[10005];

int tim = 0;

stack<int> stk;

vector<vector<int> > ccs;

void dfs(int currNode){

vis[currNode] = true;

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

stk.push(currNode);

instk[currNode] = true;

vector<int> now = ljb[currNode];

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

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

dfs(now[i]);

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

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

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

}

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

int tmp = 0;

vector<int> res;

while (currNode != tmp) {

tmp = stk.top();

res.push_back(tmp);

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

stk.pop();

instk[tmp] = false;

}

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

ccs.push_back(res);

//cout << endl;

}

int main(){

int n = 0,m = 0;

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

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

break;

}else {

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

ljb[i].clear();

}

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

int a= 0,b = 0;

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

ljb[a].push_back(b);

}

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

memset(instk, 0, sizeof(instk));

memset(dfn, 0, sizeof(dfn));

memset(low, 0, sizeof(low));

ccs.clear();

while (!stk.empty()) {

stk.pop();

}

dfs(1);

bool flag = false;

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

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

flag = true;

}

if (flag) {

cout << "Yes" << endl;

}else {

cout << "No" << endl;

}

return 0;

}

HDU 1908 Double Queue

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


using namespace std;



int main(){
    multiset<pair<int, int> > q;
    int cmd = 0;
    while (scanf(" %d",&cmd) != EOF){
        if (!cmd) {
            break;
        }else if (cmd == 1) {
            //add client
            int k,p;
            scanf(" %d %d",&k,&p);
            q.insert(make_pair(p, k));

        }else if (cmd == 2) {
            //high priority
            if(q.size()==0){
                cout << 0 << endl;
                continue;
            }
            multiset<pair<int, int> >::iterator it = q.end();
            it--;
            cout << (*it).second << endl;
            q.erase(it);

        }else if(cmd == 3){
            //low proirity
            if(q.size()==0){
                cout << 0 << endl;
                continue;
            }
            multiset<pair<int, int> >::iterator it = q.begin();
            cout << (*it).second << endl;
            q.erase(it);

        }
    }
    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(){

multiset<pair<int, int> > q;

int cmd = 0;

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

if (!cmd) {

break;

}else if (cmd == 1) {

//add client

int k,p;

scanf(" %d %d",&k,&p);

q.insert(make_pair(p, k));

}else if (cmd == 2) {

//high priority

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

cout << 0 << endl;

continue;

}

multiset<pair<int, int> >::iterator it = q.end();

it--;

cout << (*it).second << endl;

q.erase(it);

}else if(cmd == 3){

//low proirity

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

cout << 0 << endl;

continue;

}

multiset<pair<int, int> >::iterator it = q.begin();

cout << (*it).second << endl;

q.erase(it);

}

return 0;

}

那帮老逼太机智了，双端优先队列他们居然用map实现也是diao。。。

HDU 1702 ACboy needs your help again!

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


using namespace std;

int main(){
    int casecnt;
    cin >> casecnt;
    while (casecnt--) {
        int cnt;
        string type;
        cin >> cnt >> type;
        if (type == "FIFO") {
            //queue resolutions
            queue<int> q;
            while (cnt--) {
                string cmd;
                int arg;
                cin >> cmd;
                if (cmd == "IN") {
                    cin >> arg;
                    q.push(arg);
                }else{
                    if (q.size() == 0) {
                        cout << "None" << endl;
                        continue;
                    }
                    cout << q.front() << endl;
                    q.pop();
                }

            }
        }else{
            //stack resolutions
            stack<int> s;
            while (cnt--) {
                string cmd;
                int arg;
                cin >> cmd;
                if (cmd == "IN") {
                    cin >> arg;
                    s.push(arg);
                }else{
                    if (s.size() == 0) {
                        cout << "None" << endl;
                        continue;
                    }
                    cout << s.top() << endl;
                    s.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;

int main(){

int casecnt;

cin >> casecnt;

while (casecnt--) {

int cnt;

string type;

cin >> cnt >> type;

if (type == "FIFO") {

//queue resolutions

queue<int> q;

while (cnt--) {

string cmd;

int arg;

cin >> cmd;

if (cmd == "IN") {

cin >> arg;

q.push(arg);

}else{

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

cout << "None" << endl;

continue;

}

cout << q.front() << endl;

q.pop();

}

}else{

//stack resolutions

stack<int> s;

while (cnt--) {

string cmd;

int arg;

cin >> cmd;

if (cmd == "IN") {

cin >> arg;

s.push(arg);

}else{

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

cout << "None" << endl;

continue;

}

cout << s.top() << endl;

s.pop();

}

return 0;

}

STL小练习

其实手写应该会很带感

Codeforces 501 B Misha and Changing Handles

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;

int main(){
    map<string, string> id;

    int num = 0;
    cin >> num;
    while (num--) {
        string oldid,newid;
        cin >> oldid >> newid;
        bool flag = false;
        map<string,string>::iterator it;
        for (it = id.begin(); it != id.end(); it++) {
            if ((*it).second == oldid) {
                flag = true;
                (*it).second = newid;
                break;
            }
        }
        if (!flag) {
            id[oldid] = newid;
        }
    }
    cout << id.size() << endl;
    map<string,string>::iterator it;
    for (it = id.begin(); it != id.end(); it++) {
        cout << (*it).first << ' ' << (*it).second << 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;

int main(){

map<string, string> id;

int num = 0;

cin >> num;

while (num--) {

string oldid,newid;

cin >> oldid >> newid;

bool flag = false;

map<string,string>::iterator it;

for (it = id.begin(); it != id.end(); it++) {

if ((*it).second == oldid) {

flag = true;

(*it).second = newid;

break;

}

if (!flag) {

id[oldid] = newid;

}

cout << id.size() << endl;

map<string,string>::iterator it;

for (it = id.begin(); it != id.end(); it++) {

cout << (*it).first << ' ' << (*it).second << endl;

}

return 0;

}

STL小练习系列