UVA11324 The Largest Clique

很自然的想到先tarjan把强联通分量缩点，因为对于一个强联通分量，要么不选，要么全选，所以可看成一个点。

然后转化成了求DAG上的一条最长路（每一个点都有权值）。刚开始我想用dijkstra写：先把所入度为0的点都放进优先队列里，然后跑dijkstra，把所有的小于号改成大于号。

结果就WA了。

想了好半天，发现不能用dijkstra求。这和负权一样：u已经被更新了，但可能还有一条节点数很多的路径到达点u，而这个答案比当前的优，却因为u已经进过队列而更新不了。

所以只能dp。这个dp那是相当水，假设有一条边(u->v), 则dp[v] = max(dp[v], dp[u] + val[v])。然后我们从所有入度为0的点开始dp就妥了。

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<cstdlib>
  7 #include<cctype>
  8 #include<vector>
  9 #include<stack>
 10 #include<queue>
 11 using namespace std;
 12 #define enter puts("") 
 13 #define space putchar(' ')
 14 #define Mem(a, x) memset(a, x, sizeof(a))
 15 #define rg register
 16 typedef long long ll;
 17 typedef double db;
 18 const int INF = 0x3f3f3f3f;
 19 const db eps = 1e-8;
 20 const int maxn = 1e4 + 5;
 21 inline ll read()
 22 {
 23     ll ans = 0;
 24     char ch = getchar(), last = ' ';
 25     while(!isdigit(ch)) {last = ch; ch = getchar();}
 26     while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
 27     if(last == '-') ans = -ans;
 28     return ans;
 29 }
 30 inline void write(ll x)
 31 {
 32     if(x < 0) x = -x, putchar('-');
 33     if(x >= 10) write(x / 10);
 34     putchar(x % 10 + '0');
 35 }
 36 
 37 int n, m;
 38 vector<int> v[maxn];
 39 
 40 stack<int> st;
 41 bool in[maxn];
 42 int dfn[maxn], low[maxn], cnt = 0;
 43 int col[maxn], val[maxn], ccol = 0;
 44 void tarjan(int now)
 45 {
 46     dfn[now] = low[now] = ++cnt;
 47     st.push(now); in[now] = 1;
 48     for(int i = 0; i < (int)v[now].size(); ++i)
 49     {
 50         if(!dfn[v[now][i]])
 51         {
 52             tarjan(v[now][i]);
 53             low[now] = min(low[now], low[v[now][i]]);
 54         }
 55         else if(in[v[now][i]]) low[now] = min(low[now], dfn[v[now][i]]);
 56     }
 57     if(dfn[now] == low[now])
 58     {
 59         int x; ccol++;
 60         do
 61         {
 62             x = st.top(); st.pop();
 63             in[x] = 0;
 64             col[x] = ccol;
 65             val[ccol]++;
 66             
 67         }while(x != now);
 68     }
 69 }
 70 
 71 vector<int> v2[maxn];
 72 int du[maxn];
 73 void newGraph(int now)
 74 {
 75     int u = col[now];
 76     for(int i = 0; i < (int)v[now].size(); ++i)
 77     {
 78         int e = col[v[now][i]];
 79         if(u == e) continue;
 80         v2[u].push_back(e);
 81         du[e]++;
 82     }
 83 }
 84 
 85 int dis[maxn];
 86 void dp(int now)
 87 {
 88     for(int i = 0; i < (int)v2[now].size(); ++i)
 89     {
 90         if(dis[v2[now][i]] < dis[now] + val[v2[now][i]])    //算一个剪枝吧 
 91         {
 92             dis[v2[now][i]] = dis[now] + val[v2[now][i]];
 93             dp(v2[now][i]);    
 94         }
 95     }
 96 }
 97 
 98 void init()
 99 {
100     for(int i = 0; i < maxn; ++i) {v[i].clear(); v2[i].clear();}
101     while(!st.empty()) st.pop();
102     Mem(dfn, 0); Mem(low, 0); Mem(col, 0); Mem(val, 0);
103     cnt = ccol = 0;
104     Mem(du, 0); Mem(dis, 0);
105 }
106 
107 int main()
108 {
109     int T = read();
110     while(T--)
111     {
112         init();
113         n = read(); m = read();
114         for(int i = 1; i <= m; ++i)
115         {
116             int x = read(), y = read();
117             v[x].push_back(y);
118         }
119         for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i);
120         for(int i = 1; i <= n; ++i) newGraph(i);
121         for(int i = 1; i <= ccol; ++i) if(!du[i]) dis[i] = val[i], dp(i);
122         int ans = 0;
123         for(int i = 1; i <= ccol; ++i) ans = max(ans, dis[i]);
124         write(ans); enter;
125     }
126     return 0;
127 }

View Code