topcoder- strange country problem. - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

topcoder- strange country problem.

topcoder- strange country problem.# JobHunting - 待字闺中

T*72015-03-05 08:03

1 楼

TopCoder problem "StrangeCountry" used in SRM 441 (Division I Level Two)
题目看下面链接
难度不小啊。做了一个小时了。哎。

T*72015-03-05 08:03

2 楼

http://topcoder.bgcoder.com/print.php?id=2430

m*n2015-03-05 08:03

3 楼

看都看不懂,最后一个,我怎么看都是1, 为什么答案是-1?

t*r2015-03-05 08:03

4 楼

no. it cannot work.
it's like
0 --- 1 --- 2 --- 3
4 -- 5
there is no circle for one set. Cannot make them connected by doing
operation mentioned above.
So no solution, return -1

【在 m*****n 的大作中提到】

: 看都看不懂,最后一个,我怎么看都是1, 为什么答案是-1?

m*n2015-03-05 08:03

5 楼

Thanks. 刚才题意理解错了,改了一下code,结果就对了. 这道题应该不难吧.包括改错,
一共就写了30分钟.

【在 t**r 的大作中提到】

: no. it cannot work.
: it's like
: 0 --- 1 --- 2 --- 3
: 4 -- 5
: there is no circle for one set. Cannot make them connected by doing
: operation mentioned above.
: So no solution, return -1

t*r2015-03-05 08:03

6 楼

can you share your code?

错,

【在 m*****n 的大作中提到】

: Thanks. 刚才题意理解错了,改了一下code,结果就对了. 这道题应该不难吧.包括改错,
: 一共就写了30分钟.

m*n2015-03-05 08:03

7 楼

刚才又看了一下,这个code 有bug,就删掉不误导大家了.

r*72015-03-05 08:03

8 楼

觉得这个题没啥意思，operation的定义很confuse，想了十几分钟才明白他的
operation是啥。然后G的上限就50个，可以用*fs不停的算，数边就可以了。

【在 T******7 的大作中提到】

: TopCoder problem "StrangeCountry" used in SRM 441 (Division I Level Two)
: 题目看下面链接
: 难度不小啊。做了一个小时了。哎。

b*h2015-03-05 08:03

9 楼

这道题可以直接计算图里有几个联通子图，同时计算每个联通子图中环的数目，如果总
共环的数目小于子图数目-1，就返回-1，否则返回联通子图数目-1
这样应该可以吧？

H*72015-03-05 08:03

10 楼

Operation没有问题啊
四个点 destroy 两条边画两条连接四点的不同新边

★ 发自iPhone App: ChineseWeb 8.7

【在 r****7 的大作中提到】

: 觉得这个题没啥意思，operation的定义很confuse，想了十几分钟才明白他的
: operation是啥。然后G的上限就50个，可以用*fs不停的算，数边就可以了。

r*72015-03-05 08:03

11 楼

不是总的环的数目，而是大于生成树的边的数目。

【在 b****h 的大作中提到】

: 这道题可以直接计算图里有几个联通子图，同时计算每个联通子图中环的数目，如果总
: 共环的数目小于子图数目-1，就返回-1，否则返回联通子图数目-1
: 这样应该可以吧？

b*h2015-03-05 08:03

12 楼

这个和生成树中边的数目有什么关系？一个生成树中可以有很多条边，但不代表它能把
2个子图连起来啊，比如一个子图是一颗树，另外一个子图2个节点连着，这2个子图肯
定连不上啊

【在 r****7 的大作中提到】

: 不是总的环的数目，而是大于生成树的边的数目。

t*r2015-03-05 08:03

13 楼

贴个答案
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
const long long LINF = (5e18);
const int INF = (1<<30);
#define EPS 1e-6
const int MOD = 1000000007;
using namespace std;
class StrangeCountry {

public:
vector g;
bool usedV[55];
bool usedE[55][55];
bool single;

int dfs(int x) {
usedV[x] = true;
int res = 0;
for (int i=0; iif (!usedV[i] && g[x][i] == 'Y') {
single = false;
usedE[x][i] = usedE[i][x] = true;
res += dfs(i);
}
}
for (int i=0; iif (!usedE[x][i] && g[x][i] == 'Y') {
usedE[x][i] = usedE[i][x] = true;
++res;
}
}
return res;
}

int transform(vector g) {
this->g = g;
memset(usedV, false, sizeof(usedV));
memset(usedE, false, sizeof(usedE));

int noextra = 0, extra = 0;
int ans = 0;
for (int i=0; iif (usedV[i])
continue;
++ans;
single = true;
int c = dfs(i);
if (single)
return -1;
if (c == 0)
++noextra;
else
extra += c;
}
if (extra < ans - 1)
return -1;
return ans - 1;
}

// BEGIN CUT HERE
public:
void run_test(int Case)
{
if ((Case == -1) || (Case == 0))
test_case_0();
if ((Case == -1) || (Case == 1))
test_case_1();
if ((Case == -1) || (Case == 2))
test_case_2();
if ((Case == -1) || (Case == 3))
test_case_3();
if ((Case == -1) || (Case == 4))
test_case_4();
if ((Case == -1) || (Case == 5))
test_case_5();
}
private:
template string print_array(const vector &V)
{ ostringstream os;
os << "{ ";
for (typename vector::const_iterator iter = V.begin(); iter !
= V.end(); ++iter)
os << '"' << *iter << "","; os << " }";
return os.str();
}

void verify_case(int Case, const int &Expected, const int &Received)
{ cerr << "Test Case #" << Case << "...";
if (Expected == Received)
cerr << "PASSED" << endl;
else {
cerr << "FAILED" << endl;
cerr << "\tExpected: "" << Expected << '"' << endl;
cerr << "\tReceived: "" << Received << '"' << endl;
}
}
void test_case_0() { string Arr0[] = {"NY",
"YN"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0
[0]))); int Arg1 = 0; verify_case(0, Arg1, transform(Arg0)); }
void test_case_1() { string Arr0[] = {"NYYNN",
"YNYNN",
"YYNNN",
"NNNNY",
"NNNYN"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(
Arr0[0]))); int Arg1 = 1; verify_case(1, Arg1, transform(Arg0)); }
void test_case_2() { string Arr0[] = {"NYYNNNN",
"YNYNNNN",
"YYNNNNN",
"NNNNYYN",
"NNNYNYY",
"NNNYYNY",
"NNNNYYN"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof
(Arr0[0]))); int Arg1 = 1; verify_case(2, Arg1, transform(Arg0)); }
void test_case_3() { string Arr0[] = {"NYNYNNNNNNNN",
"YNYNNNNNNNNN",
"NYNYYNNNNNNN",
"YNYNNNNNNNNN",
"NNYNNYYNNNNN",
"NNNNYNYNNNNN",
"NNNNYYNNNNNN",
"NNNNNNNNYYNN",
"NNNNNNNYNYNN",
"NNNNNNNYYNNN",
"NNNNNNNNNNNY",
"NNNNNNNNNNYN"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) /
sizeof(Arr0[0]))); int Arg1 = 2; verify_case(3, Arg1, transform(Arg0)); }
void test_case_4() { string Arr0[] = {"NYNNNN",
"YNYNNN",
"NYNYNN",
"NNYNNN",
"NNNNNY",
"NNNNYN"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(
Arr0[0]))); int Arg1 = -1; verify_case(4, Arg1, transform(Arg0)); }

void test_case_5() { string Arr0[] = {"NYYNNNNNNN", "YNYNNNNNNN", "
YYNNNNNNNN", "NNNNYYNNNN", "NNNYNYNNNN", "NNNYYNNNNN", "NNNNNNNYNN", "
NNNNNNYNNN", "NNNNNNNNNY", "NNNNNNNNYN"}

; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))
); int Arg1 = -1; verify_case(5, Arg1, transform(Arg0)); }

// END CUT HERE

};
// BEGIN CUT HERE
int main() {

StrangeCountry ___test;

___test.run_test(-1);

}
// END CUT HERE

b*h2015-03-05 08:03

14 楼

这思路和我上面那个帖子一样～～

【在 t**r 的大作中提到】

: 贴个答案
: #include
: #include
: #include
: #include
: #include
: #include
: #include
: #include
: #include

t*r2015-03-05 08:03

15 楼

"这道题可以直接计算图里有几个联通子图，同时计算每个联通子图中环的数目，如果总
共环的数目小于子图数目-1，就返回-1，否则返回联通子图数目-1
这样应该可以吧？"
Yeah. This is the solution. Good explanation man.