QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#252141 | #7706. Rikka with Linker | SolitaryDream# | TL | 1ms | 3428kb | C++17 | 946b | 2023-11-15 15:57:06 | 2023-11-15 15:57:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
const int N=19;
int f[1<<N|5];
int g[N];
void solve() {
int n,m;
cin >> n >> m;
FOR(i,0,n-1) g[i]=0;
FOR(i,1,m) {
int x,y;
cin >> x >> y;
--x,--y;
g[x]|=1<<y;
}
f[0]=0;
FOR(i,1,(1<<n)-1) {
f[i]=1e9;
FOR(j,0,n-1) if((1<<j)&i) {
int c=1;
FOR(k,0,n-1) if(k!=j && ((1<<k)&i) && (g[k]&i)==g[k] && (g[k]&(i^(1<<j)))!=g[k]) {
++c;
}
// if(i==7) cerr << j << ' ' << ' ' << f[i^(1<<j)] << ' ' << c << endl;
f[i]=min(f[i],f[i^(1<<j)]+c);
}
// cerr << i << " = " << f[i] << endl;
}
cout << f[(1<<n)-1] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3428kb
input:
3 3 2 1 2 2 3 3 3 1 2 2 3 3 1 5 7 1 2 2 3 3 5 5 4 4 2 2 5 3 1
output:
3 4 6
result:
ok 3 number(s): "3 4 6"
Test #2:
score: -100
Time Limit Exceeded
input:
1000 18 93 1 6 1 13 2 1 2 8 3 6 4 8 5 4 5 6 5 9 5 10 5 11 5 12 5 13 5 18 6 2 6 4 6 16 7 1 7 2 7 3 7 9 7 10 7 13 7 15 8 6 8 9 9 5 9 8 9 10 9 13 9 14 10 1 10 3 10 4 10 5 10 6 10 8 10 11 10 13 11 1 11 2 11 3 11 4 11 6 11 7 11 9 11 12 11 14 11 15 12 1 12 2 12 4 12 6 12 10 12 13 12 14 12 16 12 17 12 18 1...