hdu 2647 Reward 拓撲排序+向前星鄰接表

傳送門：hdu 2647 REward

題目大意

有個老闆要給員工發工資，老闆很善良想滿足每個員工的要求 ，但是他很吝啬。

解題思路

先解釋一下什麼是向前星鄰接表；

一般在一個圖當中我們使用鄰接矩陣表示連個點之間是否有邊比如：E[i][v] = 1表示有邊，如果等于0表示沒有邊，但是如果資料十分大的時候就會造成空間的浪費，而且記憶體也是不夠的。那麼我們就考慮使用鄰接表了，（鄰接表和鄰接矩陣都是線性代數裡面的概念），鄰接表就是一種連結清單。我們一般是使用的時候是定義一個結構體,如下：

struct Edge{
    int v,nxt;//v儲存的是被指向的節點，nxt表示頭結點儲存的邊的序号，如果是-1表示指向空
}e[MAXN<<];//存的是邊
           

簡單地來說nxt表示的是next表示與目前邊起點一樣的另一條邊在弄的數組中的位置

比如我們構造一個有向圖：

1 2

3 4

2 3

2 4

1 3

前面的指向後面的。對應的圖如下：

我們先來看一下添加邊的代碼：

void initEdge()
{
    erear = ;
    memset(head,-,sizeof head);
    memset(OUT,,sizeof OUT);
}

void addEdge(int u,int v)
{
    e[erear].v = v;//開始節點
    e[erear].nxt = head[u];//目前節點的下一個節點指向的頭節點
    //将目前節點變為頭節點
    head[u] = erear++;
}
           

那麼建圖的過程如下：

1. 首先要有”空”邊

2. 建立第一條邊

3. 因為前三條邊都是一樣的，是以前三條邊建立之後為

4. 目前節點的上一個節點不是空節點了，就可以連接配接了

5. 建立之後如圖：

知道了這個之後我們就是通過頭節點來進行通路的，代碼如下：

for(int j=head[u];~j;j=e[j].nxt)
   {
         int v = e[j].v;
            ...
   }
           

這樣優化空間就可以了。

AC代碼

#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN =  +  ;
int out[MAXN],head[MAXN],erear;
int N,M,OUT[MAXN];
bool vis[MAXN];
struct Edge{
    int v,nxt;
}e[MAXN<<];

void initEdge()
{
    erear = ;
    memset(head,-,sizeof head);
    memset(OUT,,sizeof OUT);
}

void addEdge(int u,int v)
{
    e[erear].v = v;
    e[erear].nxt = head[u];
    head[u] = erear++;
}

int getAns()
{
    queue<int>Q;
    for(int i=;i<=N;i++)
        if(OUT[i]==) Q.push(i);
    int ranked = ,ret = -,sum = ;
    while(!Q.empty())
    {
        int tmp = Q.size();
        ret += tmp*(ranked+);
        for(int i=;i<tmp;i++)
        {
            int u = Q.front();
            sum++;
            Q.pop();
            for(int j=head[u];~j;j=e[j].nxt)
            {
                int v = e[j].v;
                if(--OUT[v] == )
                    Q.push(v);
            }
        }
        ranked++;
    }
    if(sum!=N)return -;
    return ret;
}

int main()
{
    int u,v;
    while(~scanf("%d%d",&N,&M))
    {
        initEdge();
        for(int i=;i<M;i++)
        {
            scanf("%d%d",&v,&u);
            addEdge(u,v);
            OUT[v]++;
        }
        int ans = getAns();
        printf("%d\n",ans==-?-:ans+);
    }
    return ;
}