求管理员,感觉这个题的数据是错的2333

很多人的AC解法是这样的:
```
#include <bits/stdc++.h>
using namespace std;

int fa[205], n, ans = 0;
inline int find(int i)
{
return fa[i]?fa[i] = find(fa[i]):i;
}
int main()
{
scanf("%d", &n);
memset(fa, 0, sizeof fa);
for (int i = 1; i <= n; i++)
for (int c; scanf("%d", &c), c;)
if (find(i) != find(c))
fa[find(i)] = find(c);
for (int i = 1; i <= n; i++)
if (!fa[i])
ans++;
cout << ans << endl;
return 0;
}

但是如果数据是

3
2 0
0
2 0

实际答案应该为2,然而并查集输出1
所以我写了一个卡时搜索,画风大概是:

#include <bits/stdc++.h>
using namespace std;

int g[205][205], dis[205][205], lkd[205], a[205], n;
bitset<201> linked[201], tmp, bas;
clock_t c;
int ans;
void dfs(const bitset<201> &bits, int cho = 0)
{
if (bits == 0) {
ans = min(ans, cho);
return;
}
clock_t d = clock(); if (d-c >= 700) return;
// cout << ans << " " << cho << endl;
for (int i = 1; i <= n; i++)
if (bits[a[i]] && cho + 1 < ans)
dfs(bits&(~linked[a[i]]), cho+1);
}

inline bool cmp(int a, int b)
{
return lkd[a] > lkd[b];
}

int main()
{
c = clock();
scanf("%d", &n);
memset(g, 127/3, sizeof g);
memset(dis, 127/3, sizeof g);
memset(lkd, 0, sizeof lkd);
for (int i = 1; i <= n; i++) {
g[i][i] = dis[i][i] = 0;
for (int c; scanf("%d", &c), c;) {
//cout << c << endl;
g[i][c] = 1;
}
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k]+g[k][j]);
for (int i = 1; i <= n; i++) {
a[i] = i;
tmp[i] = 1;
linked[i] = 0;
for (int j = 1; j <= n; j++)
if (dis[i][j] <= 10000) {
linked[i][j] = 1;
lkd[i]++;
//cout << i << " " << j << endl;
}
}
ans = n;
sort(a+1, a+n+1, cmp);
//for (int i = 1; i <= n; i++) cout << lkd[a[i]] << " "; cin >> a[101];
bas[0] = 1;
dfs(tmp);
cout << ans << endl;
return 0;
}
```
然而是零分。。
我的** Rp--------------------------------------- **

3 条评论

  • @ 2017-03-19 14:02:03

    已经更新P1022与P1023的数据

  • @ 2016-08-20 12:16:04

    数据大概是对的,但是非常弱。
    正解大概是强联通分量?
    这里的数据似乎强一些,可以去试试。
    UPD:似乎那里的数据也没卡掉并查集做法。。

  • @ 2016-08-20 11:07:51

    偶不是30分

  • 1

信息

ID
1023
难度
4
分类
图结构 | 强连通分量 点击显示
标签
递交数
4310
已通过
1967
通过率
46%
被复制
11
上传者