您的位置: 首页  >  IT文章  >  【AStar】初赛第一场

【AStar】初赛第一场

分类: IT文章 • 2022-05-15 15:28:39

1. All X
1.1 基本思路
k和c的范围都不大，因此可以考虑迭代找循环节，然后求余数，判定是否相等。这题还是挺简单的。
1.2 代码

 1 /* 5690 */
 2 #include <iostream>
 3 #include <sstream>
 4 #include <string>
 5 #include <map>
 6 #include <queue>
 7 #include <set>
 8 #include <stack>
 9 #include <vector>
10 #include <deque>
11 #include <bitset>
12 #include <algorithm>
13 #include <cstdio>
14 #include <cmath>
15 #include <ctime>
16 #include <cstring>
17 #include <climits>
18 #include <cctype>
19 #include <cassert>
20 #include <functional>
21 #include <iterator>
22 #include <iomanip>
23 using namespace std;
24 //#pragma comment(linker,"/STACK:102400000,1024000")
25 
26 #define sti                set<int>
27 #define stpii            set<pair<int, int> >
28 #define mpii            map<int,int>
29 #define vi                vector<int>
30 #define pii                pair<int,int>
31 #define vpii            vector<pair<int,int> >
32 #define rep(i, a, n)     for (int i=a;i<n;++i)
33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
34 #define clr                clear
35 #define pb                 push_back
36 #define mp                 make_pair
37 #define fir                first
38 #define sec                second
39 #define all(x)             (x).begin(),(x).end()
40 #define SZ(x)             ((int)(x).size())
41 #define lson            l, mid, rt<<1
42 #define rson            mid+1, r, rt<<1|1
43 
44 typedef long long LL;
45 const int maxn = 10005;
46 int x;
47 LL m;
48 int c, k;
49 int visit[maxn];
50 
51 int main() {
52     ios::sync_with_stdio(false);
53     #ifndef ONLINE_JUDGE
54         freopen("data.in", "r", stdin);
55         freopen("data.out", "w", stdout);
56     #endif
57 
58     int t;
59     int tmp, ntmp;
60     LL i, cycle;
61 
62     scanf("%d", &t);
63     rep(tt, 1, t+1) {
64         scanf("%d%I64d%d%d", &x,&m,&k,&c);
65         printf("Case #%d:
", tt);
66         memset(visit, -1, sizeof(visit));
67         ntmp = x % k;
68         cycle = -1;
69         for (i=1; i<=m; ++i) {
70             if (visit[tmp=ntmp] != -1) {
71                 cycle = i - visit[tmp];
72                 break;
73             }
74             visit[tmp] = i;
75             ntmp = (10*tmp + x) % k;
76         }
77 
78         if (cycle == -1) {
79             puts(tmp==c ? "Yes":"No");
80         } else {
81             LL n = ((m - visit[tmp]) % cycle + cycle) % cycle;
82             for (i=0; i<n; ++i)
83                 tmp = (10*tmp + x) % k;
84             puts(tmp==c ? "Yes":"No");
85         }
86     }
87 
88     #ifndef ONLINE_JUDGE
89         printf("time = %ldms.
", clock());
90     #endif
91 
92     return 0;
93 }
View Code

2. Sitting in Line
2.1 基本思路
N的范围很小，刚开始以为这是一个数学题，后来发现状态DP可解。
$dp[st][n]$st表示当前状态（即当前已经加入数字），n表示当前排列的最末端数字。显然有状态转移方程
[
  dp[nst][k] = max(dp[nst][k], dp[st|(1<<k)][j]+a_j imes a_k), \
  qquad ext{其中 } st&(1<<k) == 0 ext{ 并且 }pos_k==-1 || pos_k==getBits(st)
]
2.2 代码

  1 /* 5691 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 typedef long long LL;
 45 LL INF = 0x3f3f3f3f3f3f3f3f;
 46 LL NEG_INF = 0xc0c0c0c0c0c0c0c0;
 47 const int maxn = 16;
 48 LL dp[1<<maxn][maxn];
 49 int a[maxn], p[maxn];
 50 int Bits[1<<maxn];
 51 int n;
 52 
 53 int getBits(int x) {
 54     int ret = 0;
 55     
 56     while (x) {
 57         ret += x & 1;
 58         x >>= 1;
 59     }
 60     
 61     return ret;
 62 }
 63 
 64 void init() {
 65     const int mst = 1<<16;
 66     rep(i, 0, mst) Bits[i] = getBits(i);
 67 }
 68 
 69 void solve() {
 70     memset(dp, 0xC0, sizeof(dp));
 71     rep(i, 0, n) {
 72         if (p[i]==-1 || p[i]==0)
 73             dp[1<<i][i] = 0;
 74     }
 75     
 76     const int mst = 1<<n;
 77     #ifndef ONLINE_JUDGE
 78     printf("NEG_INF = %I64d
", NEG_INF);
 79     #endif
 80     rep(i, 0, mst) {
 81         const int idx = Bits[i];
 82         rep(j, 0, n) {
 83             if (dp[i][j] == NEG_INF) continue;
 84             rep(k, 0, n) {
 85                 if (i & (1<<k)) continue;
 86                 if (p[k]==-1 || p[k]==idx) {
 87                     int nst = i | 1<<k;
 88                     dp[nst][k] = max(dp[nst][k], dp[i][j]+a[j]*a[k]);
 89                 }
 90             }
 91         }
 92     }
 93     
 94     LL ans = NEG_INF;
 95     rep(j, 0, n)
 96         ans = max(ans, dp[mst-1][j]);
 97     printf("%I64d
", ans);
 98 }
 99 
100 int main() {
101     ios::sync_with_stdio(false);
102     #ifndef ONLINE_JUDGE
103         freopen("data.in", "r", stdin);
104         freopen("data.out", "w", stdout);
105     #endif
106     
107     int t;
108     
109     init();
110     scanf("%d", &t);
111     rep(tt, 1, t+1) {
112         scanf("%d", &n);
113         rep(i, 0, n)
114             scanf("%d%d", &a[i],&p[i]);
115         printf("Case #%d:
", tt);
116         solve();
117     }
118     
119     #ifndef ONLINE_JUDGE
120         printf("time = %ldms.
", clock());
121     #endif
122     
123     return 0;
124 }
View Code

3. Snacks
3.1 基本思路
这个题刚开始看以为是树链剖分，巨难无比，赛后发现就是个树形结构转线性结构，然后使用线段树维护最大值就好了，使用下lazy标记直接A了。
3.2 代码

  1 /* 5692 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 #pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 struct edge_t {
 45     int v, nxt;
 46 };
 47 
 48 typedef long long LL;
 49 const int maxn = 1e5+5;
 50 const int maxv = maxn;
 51 const int maxe = maxn * 2;
 52 int head[maxv], l, cnt;
 53 edge_t E[maxe];
 54 LL mx[maxn<<2], delta[maxn<<2];
 55 int L[maxn], R[maxn], a[maxn];
 56 int LLL, RR, w;
 57 int n, m;
 58 
 59 void init() {
 60     memset(head, -1, sizeof(head));
 61     l = cnt = 0;
 62     memset(mx, 0, sizeof(mx));
 63     memset(delta, 0, sizeof(delta));
 64 }
 65 
 66 void addEdge(int u, int v) {
 67     E[l].v = v;
 68     E[l].nxt = head[u];
 69     head[u] = l++;
 70     
 71     E[l].v = u;
 72     E[l].nxt = head[v];
 73     head[v] = l++;
 74 }
 75 
 76 void dfs(int u, int fa) {
 77     L[u] = ++cnt;
 78     for (int k=head[u]; k!=-1; k=E[k].nxt) {
 79         const int& v = E[k].v;
 80         if (v == fa) continue;
 81         dfs(v, u);
 82     }
 83     R[u] = cnt;
 84 }
 85 
 86 inline void PushDown(int rt) {
 87     if (delta[rt]) {
 88         int lb = rt<<1, rb = lb | 1;
 89         delta[lb] += delta[rt];
 90         delta[rb] += delta[rt];
 91         mx[lb] += delta[rt];
 92         mx[rb] += delta[rt];
 93         delta[rt] = 0;
 94     }
 95 }
 96 
 97 inline void PushUp(int rt) {
 98     mx[rt] = max(mx[rt<<1], mx[rt<<1|1]);
 99 }
100 
101 void Update(int l, int r, int rt) {
102     if (LLL<=l && RR>=r) {
103         mx[rt] += w;
104         delta[rt] += w;
105         return ;
106     }
107     
108     PushDown(rt);
109     int mid = (l + r) >> 1;
110     
111     if (RR <= mid) {
112         Update(lson);
113     } else if (LLL > mid) {
114         Update(rson);
115     } else {
116         Update(lson);
117         Update(rson);
118     }
119     
120     PushUp(rt);
121 }
122 
123 LL Query(int l, int r, int rt) {
124     if (LLL<=l && RR>=r) {
125         return mx[rt];
126     }
127     
128     PushDown(rt);
129     int mid = (l + r) >> 1;
130     
131     if (RR <= mid)
132         return Query(lson);
133     else if (LLL > mid)
134         return Query(rson);
135     else
136         return max(Query(lson), Query(rson));
137 }
138 
139 void solve() {
140     dfs(0, -1);
141     
142     rep(i, 0, n) {
143         scanf("%d", &a[i]);
144         LLL = L[i];
145         RR = R[i];
146         w = a[i];
147         Update(1, n, 1);
148     }
149     
150     int op, x, y;
151     LL ans;
152     
153     rep(i, 0, m) {
154         scanf("%d%d", &op, &x);
155         LLL = L[x];
156         RR = R[x];
157         if (op) {
158             ans = Query(1, n, 1);
159             printf("%I64d
", ans);
160         } else {
161             scanf("%d", &y);
162             y -= a[x];
163             w = y;
164             Update(1, n, 1);
165             a[x] += y;
166         }
167     }
168 }
169 
170 int main() {
171     ios::sync_with_stdio(false);
172     #ifndef ONLINE_JUDGE
173         freopen("data.in", "r", stdin);
174         freopen("data.out", "w", stdout);
175     #endif
176     
177     int t;
178     int u, v;
179     
180     scanf("%d", &t);
181     rep(tt, 1, t+1) {
182         scanf("%d%d", &n,&m);
183         init();
184         rep(i, 1, n) {
185             scanf("%d%d", &u,&v);
186             addEdge(u, v);
187         }
188         printf("Case #%d:
", tt);
189         solve();
190     }
191     
192     #ifndef ONLINE_JUDGE
193         printf("time = %ldms.
", clock());
194     #endif
195     
196     return 0;
197 }
View Code


4. D Game
4.1 基本思路
$n,m in [1,300]$这数据范围很小，基本思路是DP.
不妨令$dp[i][j]$表示从第$i$个数字到第$j$个数字能否通过全部被删掉，$mx[i]$表示前$i$个数字中可以最多可以删掉的数字。显然有动态转移方程
[
  mx[i] = max(mx[i], mx[j-1]+i-j+1), ext{ if } dp[j][i]=True
]
因此，紧急考虑$dp[j][i]$的情况即可：
(1) $dp[j][k] & dp[k+1][i], k in [j+1, i)$
(2) $dp[j+1][i-1], (a_i-a_j) in D$
(3) $dp[j+1][k-1] & dp[k+1][i-1], (a_i-a_j)/2 in D, a_k*2 = a_i+a_j, k in [j+1, i)$
4.2 代码

  1 /* 5693 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 const int maxn = 305;
 45 bool dp[maxn][maxn];
 46 int mx[maxn];
 47 int a[maxn];
 48 int n, m;
 49 sti st;
 50 
 51 void solve() {
 52     memset(dp, 0, sizeof(dp));
 53     
 54     rep(i, 1, n+1) {
 55         dp[i][i] = false;
 56         dp[i][i-1] = true;
 57         per(j, 1, i) {
 58             rep(k, j+1, i)
 59                 dp[j][i] |= dp[j][k] & dp[k+1][i];
 60             if (st.count(a[i]-a[j])) {
 61                 dp[j][i] |= dp[j+1][i-1];
 62             }
 63             if ((a[i]-a[j])%2==0 && st.count((a[i]-a[j])>>1)) {
 64                 rep(k, j+1, i) {
 65                     if (a[k]+a[k] == a[j]+a[i]) {
 66                         dp[j][i] |= dp[j+1][k-1] & dp[k+1][i-1];
 67                     }
 68                 }
 69             }
 70         }
 71     }
 72     
 73     mx[0] = 0;
 74     rep(i, 1, n+1) {
 75         mx[i] = mx[i-1];
 76         rep(j, 1, i) {
 77             if (dp[j][i])
 78                 mx[i] = max(mx[i], mx[j-1]+i-j+1);
 79         }
 80     }
 81     
 82     printf("%d
", mx[n]);
 83 }
 84 
 85 int main() {
 86     ios::sync_with_stdio(false);
 87     #ifndef ONLINE_JUDGE
 88         freopen("data.in", "r", stdin);
 89         freopen("data.out", "w", stdout);
 90     #endif
 91     
 92     int t;
 93     int x;
 94     
 95     scanf("%d", &t);
 96     while (t--) {
 97         scanf("%d%d", &n,&m);
 98         rep(i, 1, n+1) scanf("%d", a+i);
 99         st.clr();
100         rep(i, 0, m) {
101             scanf("%d", &x);
102             st.insert(x);
103         }
104         solve();
105     }
106     
107     #ifndef ONLINE_JUDGE
108         printf("time = %ldms.
", clock());
109     #endif
110     
111     return 0;
112 }
View Code


5. BD String
5.1 基本思路
不妨令$f(n)$表示$S(n)$字符串的长度，显然很容易得到$f(n) = 2^n-1$。因此，最终串的长度为$f(2^{1000}) = 2^{1001}-1$，而$L,R in [1,10^{18}]$。
显然原问题等价于计算$S(60)$的$[L,R]$范围内的B的个数。
算法很简单，就是个递归。可以考虑$S(k)$的左半部分和右半部分，递归时，加上剪枝$R-L+1==f(dep)$即可，此时B的数量为$f(dep-1)$,D的数量为$f(dep-1)-1$。
5.2 代码

  1 /* 5694 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 #pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 typedef long long LL;
 45 LL Base[62];
 46 LL L, R;
 47 
 48 void init() {
 49     rep(i, 0, 62)
 50         Base[i] = 1LL << i;
 51 }
 52 
 53 LL dfsD(LL, LL, int);
 54 LL dfsB(LL, LL, int);
 55 
 56 LL dfsD(LL L, LL R, int dep) {
 57     if (L > R)    return 0;
 58     if (dep == 0)    return 0;
 59     if (dep == 1)    return 0;
 60     
 61     if (R-L+1 == Base[dep]-1) {
 62         return Base[dep-1]-1;
 63     }
 64     LL mid = Base[dep-1];
 65     if (R < mid) {
 66         return dfsD(L, R, dep-1);
 67     } else if (L > mid) {
 68         LL nxtL = mid - 1 - (R - mid) + 1;
 69         LL nxtR = mid - 1 - (L - mid) + 1;
 70         return dfsB(nxtL, nxtR, dep-1);
 71         
 72     } else {
 73         LL lret = dfsD(L, mid-1, dep-1);
 74         LL rret = 0;
 75         
 76         if (R > mid) {
 77             LL nxtL = mid-1 - (R-mid) + 1;
 78             LL nxtR = mid-1;
 79             rret = dfsB(nxtL, nxtR, dep-1);
 80         }
 81         
 82         return lret + rret;
 83     }
 84 }
 85 
 86 LL dfsB(LL L, LL R, int dep) {
 87     if (L > R)    return 0;
 88     if (dep == 0)    return 0;
 89     if (dep == 1)    return 1;
 90     
 91     if (R-L+1 == Base[dep]-1) {
 92         return Base[dep-1];
 93     }
 94     LL mid = Base[dep-1];
 95     if (R < mid) {
 96         return dfsB(L, R, dep-1);
 97         
 98     } else if (L > mid) {
 99         LL nxtL = mid - 1 - (R - mid) + 1;
100         LL nxtR = mid - 1 - (L - mid) + 1;
101         return dfsD(nxtL, nxtR, dep-1);
102         
103     } else {
104         LL lret = dfsB(L, mid-1, dep-1);
105         LL rret = 0;
106         
107         if (R > mid) {
108             LL nxtL = mid-1 - (R-mid) + 1;
109             LL nxtR = mid-1;
110             rret = dfsD(nxtL, nxtR, dep-1);
111         }
112         
113         return lret + 1 + rret;
114     }
115 }
116 
117 void solve() {
118     LL ans = dfsB(L, R, 60);
119     
120     printf("%I64d
", ans);
121 }
122 
123 int main() {
124     ios::sync_with_stdio(false);
125     #ifndef ONLINE_JUDGE
126         freopen("data.in", "r", stdin);
127         freopen("data.out", "w", stdout);
128     #endif
129     
130     int t;
131     
132     init();
133     scanf("%d", &t);
134     while (t--) {
135         scanf("%I64d%I64d", &L, &R);
136         solve();
137     }
138     
139     #ifndef ONLINE_JUDGE
140         printf("time = %ldms.
", clock());
141     #endif
142     
143     return 0;
144 }
View Code


6. Gym Class
6.1 基本思路
水题，根据依赖性建图，然后拓扑排序就好了。注意拓扑的时候使用优先队列可求最值。
6.2 代码

  1 /*  */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <bitset>
 12 #include <algorithm>
 13 #include <cstdio>
 14 #include <cmath>
 15 #include <ctime>
 16 #include <cstring>
 17 #include <climits>
 18 #include <cctype>
 19 #include <cassert>
 20 #include <functional>
 21 #include <iterator>
 22 #include <iomanip>
 23 using namespace std;
 24 #pragma comment(linker,"/STACK:102400000,1024000")
 25 
 26 #define sti                set<int>
 27 #define stpii            set<pair<int, int> >
 28 #define mpii            map<int,int>
 29 #define vi                vector<int>
 30 #define pii                pair<int,int>
 31 #define vpii            vector<pair<int,int> >
 32 #define rep(i, a, n)     for (int i=a;i<n;++i)
 33 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 34 #define clr                clear
 35 #define pb                 push_back
 36 #define mp                 make_pair
 37 #define fir                first
 38 #define sec                second
 39 #define all(x)             (x).begin(),(x).end()
 40 #define SZ(x)             ((int)(x).size())
 41 #define lson            l, mid, rt<<1
 42 #define rson            mid+1, r, rt<<1|1
 43 
 44 struct edge_t {
 45     int v, nxt;
 46 };
 47 
 48 typedef long long LL;
 49 const int maxn = 1e5+5;
 50 const int maxv = maxn;
 51 const int maxe = maxn;
 52 int head[maxv], l;
 53 edge_t E[maxe];
 54 int deg[maxv];
 55 bool visit[maxv];
 56 int n, m;
 57 
 58 void init() {
 59     memset(head, -1, sizeof(head));
 60     memset(deg, 0, sizeof(deg));
 61     memset(visit, false, sizeof(visit));
 62     l = 0;
 63 }
 64 
 65 inline void addEdge(int u, int v) {
 66     ++deg[v];
 67     E[l].v = v;
 68     E[l].nxt = head[u];
 69     head[u] = l++;
 70 }
 71 
 72 void solve() {
 73     priority_queue<int> Q;
 74     LL ans = 0;
 75     int u, v, k, mn = INT_MAX;
 76     
 77     rep(i, 1, n+1) {
 78         if (deg[i] == 0) {
 79             Q.push(i);
 80             visit[i] = true;
 81         }
 82     }
 83     
 84     while (!Q.empty()) {
 85         u = Q.top();
 86         Q.pop();
 87         mn = min(u, mn);
 88         ans += mn;
 89         for (k=head[u]; k!=-1; k=E[k].nxt) {
 90             v = E[k].v;
 91             if (!visit[v] && --deg[v]==0) {
 92                 Q.push(v);
 93                 visit[v] = true;
 94             }
 95         }
 96     }
 97     
 98     printf("%I64d
", ans);
 99 }
100 
101 int main() {
102     ios::sync_with_stdio(false);
103     #ifndef ONLINE_JUDGE
104         freopen("data.in", "r", stdin);
105         freopen("data.out", "w", stdout);
106     #endif
107     
108     int t;
109     int u, v;
110     
111     scanf("%d", &t);
112     while (t--) {
113         scanf("%d%d", &n, &m);
114         init();
115         rep(i, 0, m) {
116             scanf("%d%d", &u,&v);
117             addEdge(u, v);
118         }
119         solve();
120     }
121     
122     #ifndef ONLINE_JUDGE
123         printf("time = %ldms.
", clock());
124     #endif
125     
126     return 0;
127 }
View Code

相关推荐