杂题小记（2023.03.13）

更好的阅读体验戳此进入

P3559 [POI2013] LAB-Maze

以前咕掉的一道阴间构造，和计算几何基本每关系，思想还是很有启发性的，构造细节过多这里就不赘述了，第一篇题解已经十分详尽细致了。

xxxxxxxxxx
151
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (110000)
24
#define LEFT (false)
25
#define RIGHT (true)
26
#define opt(i) (opt.at(i - 1))
27
#define spl(i) (spl.at(i - 1))
28

29
template < typename T = int >
30
inline T read(void);
31

32
int len[LIM]; //max len???
33

34
class Square{
35
private:
36
public:
37
    int width, height;
38
    int lenl, lenr;
39
    int idxl, idxr;
40
    int posl, posr;
41
    Square Rotate(bool dire){//Rotate the hole square.
42
        len[idxl] = len[idxl] ? len[idxl] : lenl;
43
        len[idxr] = len[idxr] ? len[idxr] : lenr;
44
        *this = Square{
45
            height,
46
            width + 2,
47
            dire == LEFT ? posl : height - posl + 1,
48
            dire == RIGHT ? posr : height - posr + 1,
49
            idxl - 1,
50
            idxr + 1,
51
            dire == LEFT ? width + 2 : 1,
52
            dire == RIGHT ? width + 2 : 1
53
        };
54
        return *this;
55
    }
56
    void Merge(Square S){
57
        len[idxr] = len[idxr] ? len[idxr] : lenr + S.lenl - 1;
58
        *this = Square{
59
            width + S.width,
60
            max(height - posr, S.height - S.posl) + max(posr, S.posl),
61
            lenl,
62
            S.lenr,
63
            idxl,
64
            S.idxr,
65
            posl + max(S.posl - posr, 0),
66
            S.posr + max(posr - S.posl, 0)
67
        };
68
    }
69
    void Print(void){
70
        printf("Square : %d %d %d %d %d %d %d %d\n", width, height, lenl, lenr, idxl, idxr, posl, posr);
71
    }
72
}sq[LIM];
73

74
string S;
75
int N;
76
int cntL, cntP;
77
basic_string < bool > opt;
78
basic_string < int > spl;
79
int dx[10] = {0,  -1, 0, 1, 0};
80
int dy[10] = {0,  0, 1, 0, -1};
81
pair < int, int > pos[LIM];
82

83
int main(){
84
    cin >> S; N = S.length();
85
    for(auto c : S)c == 'L' ? ++cntL : ++cntP;
86
    if(cntL - cntP != 4)printf("NIE\n"), exit(0);
87
    int ccnt(0); bool allP(true);
88
    for(auto c : S)if(allP && c == 'P')++ccnt; else allP = false, opt += c == 'P';
89
    for(int i = 1; i <= ccnt; ++i)opt += RIGHT;
90
    int d(0);
91
    for(int i = 1; i <= (int)opt.size() && (int)spl.size() < 4; ++i){
92
        if(!d && !opt(i))spl += i;
93
        else d += opt(i) ? -1 : 1;
94
    }
95
    auto GenerateSquare = [](int l, int r)->Square{
96
        if(l > r)return Square{0, 1, 0, 0, 0, 0, 0, 0};
97
        stack < bool > cur;
98
        sq[0] = Square();
99
        while(l <= r){
100
            if(!cur.empty() && opt(l) != cur.top()){
101
                cur.pop();
102
                if(!sq[cur.size() + 1].width)
103
                    sq[cur.size() + 1] = Square{1, 2, 1, 1, l - 1, l + 1, opt(l) ? 1 : 2, opt(l) ? 2 : 1},
104
                    len[l] = len[l] ? len[l] : 1;
105
                    // len[l] = 1;
106
                else
107
                    sq[cur.size() + 1].Rotate(opt(l));
108
                if(!sq[cur.size()].width)sq[cur.size()] = sq[cur.size() + 1];
109
                else sq[cur.size()].Merge(sq[cur.size() + 1]);
110
                sq[cur.size() + 1] = Square();
111
            }else
112
                cur.push(opt(l)), sq[cur.size()] = Square();
113
            ++l;
114
        }return sq[0];
115
    };
116
    auto InstantiateSquare = [](void)->void{
117
        pos[1] = {0, 0};
118
        int cdire(1);
119
        for(int i = 2; i <= N + 1; ++i){
120
            pos[i] = {pos[i - 1].first + dx[cdire] * len[i - 1], pos[i - 1].second + dy[cdire] * len[i - 1]};
121
            cdire += opt(i - 1) ? 1 : -1; cdire = cdire > 4 ? 1 : (cdire < 1 ? 4 : cdire);
122
        }
123
    };
124
    auto SetLen = [GenerateSquare](int idx, int l, int r)->void{len[idx] = GenerateSquare(l, r).Rotate(LEFT).lenl + LIM;};
125
    SetLen(spl(1), spl(1) + 1, spl(2) - 1), SetLen(spl(2), spl(2) + 1, spl(3) - 1),
126
    SetLen(spl(3), spl(3) + 1, spl(4) - 1), SetLen(spl(4), spl(4) + 1, N);
127
    InstantiateSquare();
128
    pos[N + 1].first > 0 ? len[spl(1)] += pos[N + 1].first : len[spl(3)] -= pos[N + 1].first;
129
    pos[N + 1].second > 0 ? len[spl(2)] += pos[N + 1].second : len[spl(4)] -= pos[N + 1].second;
130
    InstantiateSquare();
131
    for(int i = N - ccnt + 1; i <= N; ++i)printf("%d %d\n", pos[i].first, pos[i].second);
132
    for(int i = 1; i <= N - ccnt; ++i)printf("%d %d\n", pos[i].first, pos[i].second);
133
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
134
    return 0;
135
}
136

137
template < typename T >
138
inline T read(void){
139
    T ret(0);
140
    int flag(1);
141
    char c = getchar();
142
    while(c != '-' && !isdigit(c))c = getchar();
143
    if(c == '-')flag = -1, c = getchar();
144
    while(isdigit(c)){
145
        ret *= 10;
146
        ret += int(c - '0');
147
        c = getchar();
148
    }
149
    ret *= flag;
150
    return ret;
151
}

LG-P6116 [JOI 2019 Final]たのしいたのしいたのしい家庭菜園

たのしいたのしいたのしい家庭菜園 (Growing Vegetables is Fun 3)

Zpair 的模拟赛的 T1，挺有意思的 DP，考虑状态 $dp(i,j,k,t,c)$$dp(i, j, k, t, c)$ 表示共 $i$$i$ 个 $j$$j$ 个 $0$$0$，$k$$k$ 个 $1$$1$，$t$$t$ 个 $2$$2$，结尾为 $c$$c$ 的方案数，转移显然，同时发现 $t=i-j-k$$t = i - j - k$，故可优化掉一维，最终 $\mathtt{\text{3D0D}}$$\texttt{3D0D}$。

发现关键点在于这样的转移一定最优，因为同颜色间一定不会交换位置，可以通过如此状态最优地表示出整个序列的具体状态，同时方便记录转移贡献。

赛时想了个假的 DP 然后过了大样例就跑路了，最终挂了 $50\mathtt{\text{pts}}$$50\texttt{pts}$。

xxxxxxxxxx
223
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define INF (0x3f3f3f3f)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
int s[410];
30
// int dp[65][65][65][65];
31
// int dp[410][3];
32
// int nxt[410][3][410][3];
33
// basic_string < int > vals[410][3];
34

35
// class BIT{
36
// private:
37
//     int tr[10];
38
// public:
39
//     int 
40
// }
41

42

43
int dp[410][410][410][3];
44
int cnt[3][410];
45
int pos[3][410];
46

47
int main(){
48
    // freopen("stand.in", "r", stdin);
49
    // freopen("stand.out", "w", stdout);
50
    memset(dp, 0x3f, sizeof dp);
51
    N = read();
52
    // bool noneF(true);
53
    for(int i = 1; i <= N; ++i){
54
        char c = getchar(); while(!isalpha(c))c = getchar();
55
        s[i] = c == 'R' ? 0 : (c == 'G' ? 1 : 2);
56
        cnt[0][i] = cnt[0][i - 1] + (s[i] == 0);
57
        cnt[1][i] = cnt[1][i - 1] + (s[i] == 1);
58
        cnt[2][i] = cnt[2][i - 1] + (s[i] == 2);
59
        if(s[i] == 0)pos[0][cnt[0][i]] = i;
60
        if(s[i] == 1)pos[1][cnt[1][i]] = i;
61
        if(s[i] == 2)pos[2][cnt[2][i]] = i;
62
        // if(s[i] == 2)noneF = false;
63
    }
64
    dp[1][1][0][0] = pos[0][1] - 1;
65
    dp[1][0][1][1] = pos[1][1] - 1;
66
    dp[1][0][0][2] = pos[2][1] - 1;
67
    for(int i = 2; i <= N; ++i){
68
        for(int j = 0; j <= cnt[0][N]; ++j){
69
            for(int k = 0; k <= cnt[1][N]; ++k){
70
                if(i - j - k > cnt[2][N] || i - j - k < 0)continue;
71
                if(j - 1 >= 0)dp[i][j][k][0] = min(dp[i - 1][j - 1][k][1], dp[i - 1][j - 1][k][2]) + pos[0][j] + max(0, k - cnt[1][pos[0][j]]) + max(0, (i - j - k - cnt[2][pos[0][j]])) - i;
72
                if(k - 1 >= 0)dp[i][j][k][1] = min(dp[i - 1][j][k - 1][0], dp[i - 1][j][k - 1][2]) + pos[1][k] + max(0, j - cnt[0][pos[1][k]]) + max(0, (i - j - k - cnt[2][pos[1][k]])) - i;
73
                dp[i][j][k][2] = min(dp[i - 1][j][k][0], dp[i - 1][j][k][1]) + pos[2][i - j - k] + max(0, j - cnt[0][pos[2][i - j - k]]) + max(0, (k - cnt[1][pos[2][i - j - k]])) - i;
74
            }
75
        }
76
    }
77
    // for(int i = 1; i <= N; ++i)
78
    //     for(int j = 0; j <= cnt[0][N]; ++j)
79
    //         for(int k = 0; k <= cnt[1][N]; ++k)
80
    //             for(int c = 0; c <= 2; ++c)printf("dp[%d][%d][%d][%d] = %d\n", i, j, k, c, dp[i][j][k][c]);
81
    int ans = min({dp[N][cnt[0][N]][cnt[1][N]][0], dp[N][cnt[0][N]][cnt[1][N]][1], dp[N][cnt[0][N]][cnt[1][N]][2]});
82
    // for(int i = 0; i <= N; ++i){
83
    //     for(int j = 0; j <= N - i; ++j){
84
    //         for(int k = 0; k <= N - i - j; ++k){
85

86
    //             int idx = i + j + k;
87
    //             switch(s[idx]){
88
    //                 case 0:{
89
    //                     dp[i][j][k] = dp[i][]
90
    //                     break;
91
    //                 }
92
    //             }
93
    //         }
94
    //     }
95
    // }
96

97

98

99

100
    // if(N <= 8){
101
    //     int ans(INF);
102
    //     int times(1);
103
    //     for(int i = 1; i <= N; ++i)times *= i;
104
    //     while(times--){
105
    //         next_permutation(s + 1, s + N + 1);
106

107
    //     }
108
    // }
109
    // if(noneF){
110
    //     int ans(0);
111
    //     int lst(-1);
112
    //     for(int i = 1; i <= N; ++i){
113
    //         if(lst != s[i])lst = s[i];
114
    //         else{
115
    //             for(int j = i + 1; j <= N; ++j){
116
    //                 if(s[j] != lst){
117
    //                     int val = s[j];
118
    //                     for(int k = j; k >= i + 1; --k)s[k] = s[k - 1];
119
    //                     s[i] = val;
120
    //                     ans += (j - i);
121
    //                     lst = val;
122
    //                     break;
123
    //                 }
124
    //                 if(j == N)printf("-1\n"), exit(0);
125
    //             }
126
    //         }
127
    //     }printf("%d\n", ans);
128
    //     exit(0);
129
    // }
130
    // for(int i = 1; i <= N; ++i)vals[0][0] += s[i];
131
    // int end[3] = {0, 0, 0};
132
    // for(int c = N; c >= 1; --c){
133
    //     end[vals[0][0].at(c - 1)] = c;
134
    //     nxt[0][0][c][0] = end[0],
135
    //     nxt[0][0][c][1] = end[1],
136
    //     nxt[0][0][c][2] = end[2];
137
    // }
138
    // vals[1][0] = vals[1][1] = vals[1][2] = vals[0][0];
139
    // for(int j = 0; j <= 2; ++j){
140
    //     dp[1][j] = nxt[0][0][1][j] - 1;
141
    //     vals[1][j].erase(next(vals[1][j].begin(), nxt[0][0][1][j] - 1));
142
    //     vals[1][j].insert(next(vals[1][j].begin(), 0), j);
143
    //     int end[3] = {0, 0, 0};
144
    //     for(int c = N; c >= 1; --c){
145
    //         end[vals[0][0].at(c - 1)] = c;
146
    //         nxt[1][j][c][0] = end[0],
147
    //         nxt[1][j][c][1] = end[1],
148
    //         nxt[1][j][c][2] = end[2];
149
    //     }
150
    // }
151
    // for(int i = 1; i <= N; ++i){
152
    //     for(int j = 0; j <= 2; ++j){
153
    //         for(int k = 0; k <= 2; ++k){
154
    //             if(j == k || !nxt[i][j][i + 1][k] || dp[i][j] >= INF)continue;
155
    //             // printf("Making i = %d, j = %d, k = %d\n",i, j, k);
156
    //             if(dp[i][j] + (nxt[i][j][i + 1][k] - i) < dp[i + 1][k]){
157
                    
158
    //                 dp[i + 1][k] = dp[i][j] + (nxt[i][j][i + 1][k] - (i + 1));
159
    //                 vals[i + 1][k] = vals[i][j];
160
    //                 // swap(vals[i + 1][k].at(i + 1), vals[i + 1][k].)
161
    //                 vals[i + 1][k].erase(next(vals[i + 1][k].begin(), nxt[i][j][i + 1][k] - 1));
162
    //                 vals[i + 1][k].insert(next(vals[i + 1][k].begin(), i + 1 - 1), k);
163
    //                 int end[3] = {0, 0, 0};
164
    //                 for(int c = N; c >= i + 1; --c){
165
    //                     end[vals[i + 1][k].at(c - 1)] = c;
166
    //                     nxt[i + 1][k][c][0] = end[0],
167
    //                     nxt[i + 1][k][c][1] = end[1],
168
    //                     nxt[i + 1][k][c][2] = end[2];
169
    //                 }
170
    //             }
171
    //         }
172
    //     }
173
    // }
174

175
    // // for(int i = 1; i <= N; ++i)
176
    // //     for(int j = 0; j <= 2; ++j)
177
    // //         printf("%d%c", dp[i][j], j == 2 ? '\n' : ' ');
178

179
    // int ans(INF);
180
    // for(int i = 0; i <= 2; ++i)ans = min(ans, dp[N][i]);
181
    printf("%d\n", ans >= INF ? -1 : ans);
182

183

184
    // for(int i = 1; i <= N; ++i){
185
    //     for(int a = 0; a <= i; ++a){
186
    //         for(int b = 0; b <= i; ++b){
187
    //             for(int c = 0; c <= i; ++c){
188
    //                 if(a == b || b == c || a == c)continue;
189
    //                 switch(s[i + 1]){
190
    //                     case 0:{
191
    //                         if(a == i)dp[i + 1][]
192
    //                         break;
193
    //                     }
194
    //                 }
195
    //             }
196
    //         }
197
    //     }
198
    // }
199

200
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
201
    return 0;
202
}
203

204
template < typename T >
205
inline T read(void){
206
    T ret(0);
207
    int flag(1);
208
    char c = getchar();
209
    while(c != '-' && !isdigit(c))c = getchar();
210
    if(c == '-')flag = -1, c = getchar();
211
    while(isdigit(c)){
212
        ret *= 10;
213
        ret += int(c - '0');
214
        c = getchar();
215
    }
216
    ret *= flag;
217
    return ret;
218
}
219

220
/*
221
20
222
BBGBBBGGGGFGBBGFGFBG
223
*/

[AGC013D] Piling Up

朴素 DP 考虑令 $dp(i,j)$$dp(i, j)$ 表示前 $i$$i$ 个操作最终 $x_i=j$$x_i = j$ 的方案数，转移即考虑四种操作即可。发现有重复，考虑抽象成折线后又多个形状相同的折线，去重考虑令 $f(i,j)$$f(i, j)$ 表示同上状态但过程中不能达到 $x_i=0$$x_i = 0$ 的方案数，$g(i,j)$$g(i, j)$ 则是钦定必须达到的方案数，简单转移后答案即为 $\sum g(m,j)$$\sum g(m, j)$。

xxxxxxxxxx
68
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (ll)(1e9 + 7)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N, M;
29
ll F[3100][3100], G[3100][3100];
30

31
int main(){
32
    N = read(), M = read();
33
    for(int i = 1; i <= N; ++i)F[0][i] = 1;
34
    G[0][0] = 1;
35
    for(int i = 1; i <= M; ++i)
36
        for(int j = 0; j <= N; ++j){
37
            if(j - 1 >= 0){
38
                (F[i][j] += F[i - 1][j - 1]) %= MOD;
39
                (G[i][j] += G[i - 1][j - 1] + G[i - 1][j]) %= MOD;
40
                ((j == 1 ? G[i][j] : F[i][j]) += F[i - 1][j]) %= MOD;
41
            }
42
            if(j + 1 <= N){
43
                (G[i][j] += G[i - 1][j + 1] + G[i - 1][j]) %= MOD;
44
                j == 0 ? (G[i][j] += F[i - 1][j + 1]) %= MOD : (F[i][j] += F[i - 1][j + 1] + F[i - 1][j]) %= MOD;
45
            }
46
        }
47
    ll ans(0);
48
    for(int i = 0; i <= N; ++i)(ans += G[M][i]) %= MOD;
49
    printf("%lld\n", ans);
50
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
51
    return 0;
52
}
53

54
template < typename T >
55
inline T read(void){
56
    T ret(0);
57
    int flag(1);
58
    char c = getchar();
59
    while(c != '-' && !isdigit(c))c = getchar();
60
    if(c == '-')flag = -1, c = getchar();
61
    while(isdigit(c)){
62
        ret *= 10;
63
        ret += int(c - '0');
64
        c = getchar();
65
    }
66
    ret *= flag;
67
    return ret;
68
}

LG-P3386 【模板】二分图最大匹配

没写过匈牙利，写一下试试。

xxxxxxxxxx
80
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
// #define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template < typename T = int >
26
inline T read(void);
27

28
int N, M, E;
29
struct Edge{
30
    Edge* nxt;
31
    int to;
32
    OPNEW;
33
}ed[110000];
34
ROPNEW;
35
Edge* head[51000];
36
bitset < 51000 > vis;
37
int match[51000];
38
int ans(0);
39

40
int main(){
41
    N = read(), M = read(), E = read();
42
    for(int i = 1; i <= E; ++i){
43
        int s = read(), t = read();
44
        head[s] = new Edge{head[s], t};
45
    }
46
    auto dfs = [](auto&& self, int p)->bool{
47
        for(auto i = head[p]; i; i = i->nxt){
48
            if(!vis[SON]){
49
                vis[SON] = true;
50
                if(!match[SON] || self(self, match[SON])){
51
                    match[SON] = p;
52
                    return true;
53
                }
54
            }
55
        }return false;
56
    };
57
    for(int i = 1; i <= N; ++i){
58
        vis.reset();
59
        if(dfs(dfs, i))++ans;
60
    }printf("%d\n", ans);
61

62
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
63
    return 0;
64
}
65

66
template < typename T >
67
inline T read(void){
68
    T ret(0);
69
    int flag(1);
70
    char c = getchar();
71
    while(c != '-' && !isdigit(c))c = getchar();
72
    if(c == '-')flag = -1, c = getchar();
73
    while(isdigit(c)){
74
        ret *= 10;
75
        ret += int(c - '0');
76
        c = getchar();
77
    }
78
    ret *= flag;
79
    return ret;
80
}

LG-P1129 [ZJOI2007] 矩阵游戏

网络流，经典建模，考虑建源点对所有行连边，所有列对汇点连边，为 $1$$1$ 的对行列连边，跑最大流判一下是否为 $n$$n$ 即可。

xxxxxxxxxx
104
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
struct Edge{
27
    Edge* nxt;
28
    Edge* rev;
29
    int to;
30
    int val;
31
    OPNEW;
32
}ed[2100000];
33
ROPNEW;
34
Edge* head[81000];
35
Edge* curh[81000];
36
int N;
37
int S, T;
38
int dep[81000];
39

40
int main(){
41
    auto bfs = [](void)->bool{
42
        memset(dep, 0, sizeof dep);
43
        copy(head + 1, head + (N << 1) + 2 + 1, curh + 1);
44
        queue < int > cur;
45
        cur.push(T); dep[T] = 1;
46
        while(!cur.empty()){
47
            int p = cur.front(); cur.pop();
48
            for(auto i = head[p]; i; i = i->nxt)
49
                if(i->rev->val > 0 && !dep[SON])
50
                    dep[SON] = dep[p] + 1, cur.push(SON);
51
        }return dep[S];
52
    };
53
    auto dfs = [](auto&& self, int p = S, int flow = INT_MAX)->int{
54
        if(p == T)return flow;
55
        int mxflow(0);
56
        for(auto &i = curh[p]; i; i = i->nxt){
57
            if(i->val <= 0 || dep[SON] != dep[p] - 1)continue;
58
            int cflow = self(self, SON, min(i->val, flow - mxflow));
59
            mxflow += cflow;
60
            i->val -= cflow, i->rev->val += cflow;
61
            if(mxflow == flow)break;
62
        }return mxflow;
63
    };
64
    auto Dinic = [bfs, dfs](void)->int{
65
        int ret(0), tmp;
66
        while(bfs())while((tmp = dfs(dfs)))ret += tmp;
67
        return ret;
68
    };
69
    int Ts = read();
70
    while(Ts--){
71
        memset(head, 0, sizeof head);
72
        N = read();
73
        S = (N << 1) | 1, T = S + 1;
74
        auto add = [](int s, int t, int v)->void{
75
            head[s] = new Edge{head[s], npt, t, v};
76
            head[t] = new Edge{head[t], npt, s, 0};
77
            head[s]->rev = head[t], head[t]->rev = head[s];
78
        };
79
        for(int i = 1; i <= N; ++i)add(S, i, 1), add(i + N, T, 1);
80
        for(int i = 1; i <= N; ++i)
81
            for(int j = 1; j <= N; ++j)
82
                if(read())add(i, j + N, 1);
83
        auto ret = Dinic();
84
        printf("%s\n", ret == N ? "Yes" : "No");
85
    }
86
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
87
    return 0;
88
}
89

90
template < typename T >
91
inline T read(void){
92
    T ret(0);
93
    int flag(1);
94
    char c = getchar();
95
    while(c != '-' && !isdigit(c))c = getchar();
96
    if(c == '-')flag = -1, c = getchar();
97
    while(isdigit(c)){
98
        ret *= 10;
99
        ret += int(c - '0');
100
        c = getchar();
101
    }
102
    ret *= flag;
103
    return ret;
104
}

UPD

update-2023_03_13 初稿