poj 3160

Father Christmas flymouse
题意：飞鼠想给大家发礼物，收到礼物后大家给飞鼠的满足程度都已数量化（有正有负）。每个人都住一个房间，房间之间的路是单向的，飞鼠可以选任一个点为起点，路可以重复走，房间不能重复访问，但可以经过而不访问。现在问飞鼠得到的满足程度最大会是多少？

分析：负分的房间肯定不访问。强连通分支可以缩点，缩成的点的分数取所有正分房间的总和，缩点后的图就变成若干个单向连通分支，由出度为零的点倒推即可算得最大值。

View Code

  1 #include<cstdio>
  2 #include<vector>
  3 #include<stack>
  4 #include<algorithm>
  5 using namespace std;
  6 int low[30000],num[30000],comfort[30000],total[30000],ans[30000],counter,set[30000],sn,n,m,in[30000],max_ans;
  7 vector<int> group[30000],arc[30000],reverse_arc[30000];
  8 bool visited[30000],instack[30000];
  9 stack<int> connect,start;
 10 void tarjan(int u)
 11 {
 12     int i,v;
 13     connect.push(u);
 14     instack[u]=true;
 15     visited[u]=true;
 16     low[u]=num[u]=++counter;
 17     for(i=0;i<arc[u].size();i++)
 18     {
 19         v=arc[u][i];
 20         if(!visited[v])
 21         {
 22             tarjan(v);
 23             if(low[u]>low[v])
 24                 low[u]=low[v];
 25         }
 26         else if(instack[v] && low[u]>num[v])
 27             low[u]=num[v];
 28     }
 29     if(num[u]==low[u])
 30     {
 31         total[sn]=0;
 32         do
 33         {
 34             v=connect.top();
 35             connect.pop();
 36             set[v]=sn;
 37             group[sn].push_back(v);
 38             instack[v]=false;
 39             if(comfort[v]>0)
 40                 total[sn]+=comfort[v];
 41         }while(u!=v);
 42         ans[sn]=total[sn];
 43         sn++;
 44     }
 45 }
 46 void backtrace(int u)//on condiction of indegree[u]==0
 47 {
 48     int i,v;
 49     for(i=0;i<reverse_arc[u].size();i++)
 50     {
 51         v=reverse_arc[u][i];
 52         if(ans[v]<ans[u]+total[v])
 53             ans[v]=ans[u]+total[v];
 54         in[v]--;
 55         if(in[v]==0)
 56             start.push(v);
 57     }
 58     if(max_ans<ans[u])
 59         max_ans=ans[u];
 60 }
 61 int main()
 62 {
 63     int i,u,v;
 64     while(~scanf("%d%d",&n,&m))
 65     {
 66         for(i=0;i<n;i++)
 67         {
 68             visited[i]=false;
 69             instack[i]=false;
 70             scanf("%d",&comfort[i]);
 71         }
 72         for(i=0;i<m;i++)
 73         {
 74             scanf("%d%d",&u,&v);
 75             arc[u].push_back(v);
 76         }
 77         counter=sn=0;
 78         for(i=0;i<n;i++)
 79         {
 80             if(!visited[i])
 81                 tarjan(i);
 82         }
 83         //reverse_arc
 84         for(i=0;i<sn;i++)
 85             in[i]=0;
 86         for(u=0;u<n;u++)
 87         {
 88             for(i=0;i<arc[u].size();i++)
 89             {
 90                 v=arc[u][i];
 91                 if(set[v]!=set[u] && find(reverse_arc[set[v]].begin(),reverse_arc[set[v]].end(),set[u])==reverse_arc[set[v]].end())
 92                 {
 93                     reverse_arc[set[v]].push_back(set[u]);
 94                     in[set[u]]++;
 95                 }
 96             }
 97         }
 98         for(i=0;i<sn;i++)
 99         {
100             if(in[i]==0)
101                 start.push(i);
102         }
103         max_ans=0;
104         while(!start.empty())
105         {
106             u=start.top();
107             start.pop();
108             backtrace(u);
109         }
110         for(i=0;i<sn;i++)
111         {
112             reverse_arc[i].clear();
113             group[i].clear();
114         }
115         for(i=0;i<n;i++)
116             arc[i].clear();
117         printf("%d\n",max_ans);
118     }
119     return 0;
120 }