Icontofig 's Blog // 我们的征程是星辰大海！Away From OI，Come to ICPC（查看友链请点About Me）

别问我为什么写这么水的题解，问就是为了那门水的不行的专业选修课。

很简单，这个图肯定是个DAG(请不要问为什么，自己看一下题目描述。。。)

然后我们在这个DAG上按拓扑序来进行DP就可以了，因为入度为0的点一定最多游览一个，然后不断类似SPFA最长路一样的进行DP，就可以求出到某个城市最多可以游览的城市数目了。

#include <bits/stdc++.h> using namespace std; int get_num(){ int num = 0; char c; bool flag = false; while((c = getchar()) == ' ' || c == '\r' || c == '\n'); if(c == '-') flag = true; else num = c - '0'; while(isdigit(c = getchar())) num = (num<<3) + (num<<1) + c - '0'; return (flag ? -1 : 1) * num; } int n,m; int x,y; const int maxn = 1e5+5; vector<int>g[maxn]; int f[maxn],d[maxn]; int inq[maxn]; int main(){ memset(d,0,sizeof(d)); n = get_num(); m = get_num(); for(int i = 1;i <= m;++i){ x = get_num(); y = get_num(); g[x].push_back(y); d[y]++; } queue<int>q; for(int i = 1;i <= n;++i){ if(!d[i]) q.push(i),inq[i] = 1; f[i] = 1; } while(!q.empty()){ int x = q.front(); q.pop();

2019-02-26 18:14:48 | 0 Comments
| topsort

Teacher Mai has a kingdom consisting of n cities. He has planned the transportation of the kingdom. Every pair of cities has exactly a one-way road.

He wants develop this kingdom from one city to one city.

Teacher Mai now is considering developing the city w. And he hopes that for every city u he has developed, there is a one-way road from u to w, or there are two one-way roads from u to v, and from v to w, where city v has been developed before.

He gives you the map of the kingdom. Hope you can give a proper order to develop this kingdom.

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains an integer n (1<=n<=500).

The following are n lines, the i-th line contains a string consisting of n characters. If the j-th characters is 1, there is a one-way road from city i to city j.

Cities are labelled from 1.

If there is no solution just output "-1". Otherwise output n integers representing the order to develop this kingdom.

BUPT校内训练&CodeChef - VRTXCOVR-Vertex Cover 2-SAT

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.

Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2*i and 2*i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).

Determine if a valid partition exists. If it exists, provide an example of one valid partition.

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.

Each of the following M lines contains two space-se

0:00