summer holiday(顶点数最小点基和权最小点基).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define NMAX 1100

vector< vector< int > > path;
vector< vector< int > > dag;
queue< int > SQ;
int n ,m , scc, step;
int order[NMAX], order_pos, id[NMAX];
int order2[NMAX], order2_pos;
int vis[NMAX];
int out_degre[NMAX];
int cost[NMAX];
int sel[NMAX];
int min_num, min_cost;

void dfs(int pos)
{
    int i,j,next,l,pre;

    vis[pos] = step ++;
    order[ order_pos ++ ] = pos;
    order2[ order2_pos ++ ] = pos;
    l = path[pos].size();
    for (i=0;i<l;i++) {
        next = path[pos][i];
        if (vis[next] == 0) {
            dfs(next);
        }
        else if (id[next] == 0) {//have a circle and belong to nothing
            while (vis[ order2[order2_pos -1] ] > vis[next]) {//back to begin of circle
                order2_pos --;
            }
        }
    }//for i
    if (order2[order2_pos -1] == pos) {//if pos back to begin of scc
        order2_pos --;
    }
    else {
        return ;
    }
    do {//record scc
        pre = order[order_pos -1];
        id[pre] = scc;
        order_pos --;
    } while(pre != pos);
    scc ++;
}

void Gabow()
{
    int i,j,l;
    //dfs in original graph
    memset(id, 0, sizeof(id));
    memset(vis, 0, sizeof(vis));
    scc = step = 1;
    order_pos = order2_pos = 0;
    for (i=1; i<=n ;i++) {
        if (vis[i] == 0) {
            dfs(i);
        }
    }
    scc --;
}

void top_sort()
{
    int i,j,k,l,m = 0;
    memset(out_degre,0,sizeof(out_degre));
    memset(sel, 0x7f,sizeof(sel));
    l = SQ.size();
    while (l --) {
        SQ.pop();
    }
    for (i=1;i<=n;i++) {
        int id1 = id[i];
        l = path[i].size();
        for (j=0;j<l;j++) {
            int id2 = id[ path[i][j] ];
            if (id1 != id2) {
                out_degre[id2] ++;
                dag[id1].push_back(id2);
            }
        }
    }
    for (i=1;i<=scc;i++) {
        if (out_degre[i] == 0) {
            SQ.push(i);
        }
    }
    while (!SQ.empty()) {
        int now = SQ.front();
        SQ.pop();
        l = dag[now].size();
        for (i=0;i<l;i++) {
            int next = dag[now][i];
            out_degre[next] --;
            if (out_degre[next] == 0) {
                SQ.push(next);
                m --;//find non-hightest scc
                sel[next] = -1;
            }
        }
    }
    for (i=1;i<=n;i++) {
        if (sel[ id[i] ] != -1) {//selection mininum cost in the highest scc
            sel[ id[i] ] = sel[ id[i] ] > cost[i] ? cost[i] : sel[ id[i] ];
        }
    }
    min_cost = 0;
    for (i=1;i<=scc;i++) {
        if (sel[i] != -1) {
            min_cost += sel[i];
        }
    }
    min_num = scc+m;
}

int main()
{
    int i,x,y;
    path.resize(NMAX);
    dag.resize(NMAX);
    while (scanf("%d %d",&n, &m)==2) {
        for (i=0;i<=n;i++) {
            path[i].clear();
            dag[i].clear();
        }
        for (i=1;i<=n;i++) {
            scanf("%d", cost+i);
        }
        for (i=1;i<=m;i++) {
            scanf("%d %d", &x,&y);
            path[x].push_back(y);
        }
        Gabow();
        top_sort();
        //min_num : mininum vertex number
        //min_cost : mininum cost
        printf("%d %d\n", min_num, min_cost);
    }
}