1242 - Necklace

All about problems in Volume 12. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

1242 - Necklace

Post by brianfry713 » Thu Sep 04, 2014 9:53 pm

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 1242 - Necklace

Post by jddantes » Tue Dec 26, 2017 3:21 pm

Does doing BFS twice (making sure to not use an edge twice) work?
My code matches Morass' output on uDebug.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;
typedef tuple<int,int,int> t3;

bool edge_used[100000+10];

vector<vector<pi>> adjList;  // adj, edge_id

int N,M;
int S,T;

bool vis[10000+10];
pi pred[10000+10];
bool augment(){
    bool found = false;

    queue<t3> que; // node, pre, edge
    que.push(t3(S,-1, -1)); 
    memset(vis, 0, sizeof vis);

    while(!que.empty()){
        t3 t = que.front();
        que.pop();

        int node = get<0>(t);
        int pre = get<1>(t);
        int edge = get<2>(t);

        if(vis[node]) continue;
        pred[node] = pi(pre, edge);
        vis[node] = true;

        if(node == T){
            found = true;
            break;
        }

        for(auto p : adjList[node]){
            int adj = p.first;
            int eid = p.second;

            if(vis[adj]) continue;
            if(edge_used[eid]) continue;

            que.push(t3(adj, node, eid));
        }
    }

    if(found){
        int cur = T;
        while(1){
            int pre = pred[cur].first;
            int eid  =pred[cur].second;

            edge_used[eid] = true;

            if(pre == S) break;
            cur = pre;
        }
    }

    return found;
}

int main(){
    int cn = 0;
    while(scanf("%d %d",&N, &M)!=EOF){
        if(!N && !M) break;
        cn++;

        adjList.assign(N, vector<pi>());

        for(int x = 0; x<M; x++){
            int u,v;
            scanf("%d %d", &u, &v);
            u--;
            v--;
            adjList[u].push_back(pi(v, x));
            adjList[v].push_back(pi(u, x));
        }
        scanf("%d %d", &S, &T);
        S--;
        T--;
        memset(edge_used, 0, sizeof edge_used);

        int ctr = 0;
        while(1){
            bool r = augment();
            if(!r) break;
            if(r){
                ctr++;
                if(ctr == 2){
                    break;
                }
            }
        }

        printf("Case %d: %s\n", cn, ctr == 2 ? "YES": "NO");
    }


    return 0;
}

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 1242 - Necklace

Post by jddantes » Tue Dec 26, 2017 4:01 pm

Nevermind, I now know why that scheme will fail.

Post Reply

Return to “Volume 12 (1200-1299)”