Ice_cream’s world II

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3231 Accepted Submission(s): 761


Problem Description After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.
Input Every case have two integers N and M (N<=1000, M<=10000), the cities numbered 0…N-1, following M lines, each line contain three integers S, T and C, meaning from S to T have a road will cost C.
Output If no location satisfy the queen’s require, you must be output “impossible”, otherwise, print the minimum cost in this project and suitable city’s number. May be exist many suitable cities, choose the minimum number city. After every case print one blank.

Sample Input

3 1
0 1 1

4 4
0 1 10
0 2 10
1 3 20
2 3 30

Sample Output

impossible

40 0

Author Wiskey
Source HDU 2007-10 Programming Contest_WarmUp
最小樹形圖。。。。 下面所有代碼的注釋全是別人的。。至今還不是很懂。先貼個以後回來再附上自己的thinking。

#include
using namespace std;
#include
#include
#define MAXN 1005
#define INF 0x7f7f7f7f
typedef __int64 type;
struct node//邊的權和頂點
{
    int u, v;
    type w;
} edge[MAXN * MAXN];
int pre[MAXN], id[MAXN], vis[MAXN], n, m, pos;
type in[MAXN];//存最小入邊權,pre[v]為該邊的起點
type Directed_MST(int root, int V, int E)
{
    type ret = 0;//存最小樹形圖總權值
    while(true)
    {
        int i;
        //1.找每個節點的最小入邊
        for( i = 0; i < V; i++)
            in[i] = INF;//初始化為無窮大
        for( i = 0; i < E; i++)//遍歷每條邊
        {
            int u = edge[i].u;
            int v = edge[i].v;
            if(edge[i].w < in[v] && u != v)//說明頂點v有條權值較小的入邊  記錄之
            {
                pre[v] = u;//節點u指向v
                in[v] = edge[i].w;//最小入邊
                if(u == root)//這個點就是實際的起點
                    pos = i;
            }
        }
        for( i = 0; i < V; i++)//判斷是否存在最小樹形圖
        {
            if(i == root)
                continue;
            if(in[i] == INF)
                return -1;//除了根以外有點沒有入邊,則根無法到達它  說明它是獨立的點 一定不能構成樹形圖
        }
        //2.找環
        int cnt = 0;//記錄環數
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        in[root] = 0;
        for( i = 0; i < V; i++) //標記每個環
        {
            ret += in[i];//記錄權值
            int v = i;
            while(vis[v] != i && id[v] == -1 && v != root)
            {
                vis[v] = i;
                v = pre[v];
            }
            if(v != root && id[v] == -1)
            {
                for(int u = pre[v]; u != v; u = pre[u])
                    id[u] = cnt;//標記節點u為第幾個環
                id[v] = cnt++;
            }
        }
        if(cnt == 0)
            break; //無環   則break
        for( i = 0; i < V; i++)
            if(id[i] == -1)
                id[i] = cnt++;
        //3.建立新圖   縮點,重新標記
        for( i = 0; i < E; i++)
        {
            int u = edge[i].u;
            int v = edge[i].v;
            edge[i].u = id[u];
            edge[i].v = id[v];
            if(id[u] != id[v])
                edge[i].w -= in[v];
        }
        V = cnt;
        root = id[root];
    }
    return ret;
}
int main()
{
    int i;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        type sum = 0;
        for( i = 0; i < m; i++)
        {
            scanf("%d%d%I64d", &edge[i].u, &edge[i].v, &edge[i].w);
            edge[i].u++;
            edge[i].v++;
            sum += edge[i].w;
        }
        sum ++;
        for( i = m; i < m + n; i++)//增加超級節點0,節點0到其余各個節點的邊權相同（此題中 邊權要大於原圖的總邊權值）
        {
            edge[i].u = 0;
            edge[i].v = i - m + 1;
            edge[i].w = sum;
        }
        type ans = Directed_MST(0, n + 1, m + n);
        //n+1為總結點數,m+n為總邊數
        //ans代表以超級節點0為根的最小樹形圖的總權值,
        //將ans減去sum,如果差值小於sum,說明節點0的出度只有1,說明原圖是連通圖
        //如果差值>=sum,那麼說明節點0的出度不止為1,說明原圖不是連通圖
        if(ans == -1 || ans - sum >= sum)
            puts("impossible");
        else
            printf("%I64d %d\n",ans - sum, pos - m);
        puts("");
    }
    return 0;
}