ZZDoctor

390

#include <iostream>

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<vector<int>> outvec(100010, vector<int>());
vector<int> invec(100010, 0);
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int start; int end;
cin >> start >> end;
invec[end]++;
outvec[start].push_back(end);
}
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (invec[i] == 0)
{
q.push(i);
}
}

vector<int>  ret;
while (!q.empty()) {
int idx = q.front();
q.pop();

ret.push_back(idx);
for (auto& e : outvec[idx]) {
if (e != -1) {
invec[e]--;
if (invec[e] == 0) {
q.push(e);
}
e = -1;
}
}
}

if(ret.size() == n)
for (auto& e : ret) {
cout << e << " ";
}
else
cout << -1;

return 0;
}


#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], d[N], idx, ne[N];
int n, m, q[N];

{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

int bfs()
{
int hh = 0, tt = 0;

q[0] = 1;
memset(d, -1, sizeof d);
d[1] = 0;
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
d[j] = d[t] + 1;
q[++tt] = j;
}
}
}
return d[n];
}

int main(void)
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
}
cout << bfs() << endl;
return 0;
}



#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 2 * N;

int h[N];
int e[M];
int ne[M];
int idx;
int n;
int ans = N;
bool st[N];void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) {
int res = 0;
st[u] = true;
int sum = 1;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
int s = dfs(j);
res = max(res, s);
sum += s;
}
}

res = max(res, n - sum);
ans = min(res, ans);
return sum;
}

int main() {
memset(h, -1, sizeof h);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
}
dfs(1);
cout << ans << endl;

return 0;
}


# POJ1160 Post Office

10 5
1 2 4 6 7 10 11 25 44 70


11


$1 <= n <= 300$
$1 <= m <= 30$
$m <= n$
$1 <= X <= 10000$

$dp[k][j - 1]$，因为我们可以把$k$前面的别墅分成一块$k$到$i$的别墅另外分成一块，这一块只建一个超市。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 305
#define INF 0x3f3f3f3f
int V, P;
int x[MAXN], dp[MAXN][MAXN], dis[MAXN][MAXN];
int main()
{
scanf("%d %d", &V, &P);
memset(dp, INF, sizeof(dp));
for(int i = 1; i <= V; i++)
scanf("%d", &x[i]);
for(int i = 1; i <= V; i++)
dis[i][i] = 0;
for(int i = 1; i <= V; i++)
for(int j = i + 1; j <= V; j++)
dis[i][j] = dis[i][j - 1] + x[j] - x[(i + j) / 2];
for(int i = 1; i <= V; i++)
dp[i][1] = dis[1][i];
for(int j = 1; j <= P; j++)
for(int i = j + 1; i <= V; i++)
for(int k = 1; k <= i; k++)
dp[i][j] = min(dp[i][j], dp[k][j - 1] + dis[k + 1][i]);
cout << dp[V][P] << endl;
return 0;
}


#include<cstring>
#include<iostream>
#include<queue>
using namespace std;

int fact[9];
bool vis[362880];

int permutation_hash(char s[])
{
int ans = 0;
for(int i = 0; i < 9; i ++)
{
int d = 0;
for(int j = 0; j < i; j ++)
if(s[j] > s[i])  d ++;
ans += d * fact[i];
}
return ans;
}

typedef struct{
char s[10];
int step;
int k;
}Point;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0,-1, 0, 1};
int bfs(Point p)
{
vis[permutation_hash(p.s)] = true;
queue<Point> q;
q.push(p);
while(!q.empty())
{
p = q.front();
q.pop();
if(!strcmp(p.s , "12345678x"))
return p.step;
int x = p.k / 3;
int y = p.k % 3;
Point next;
next.step = p.step + 1;
for(int i = 0; i < 4; i ++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2)
{
next.k = nx * 3 + ny;
strcpy(next.s, p.s);
next.s[9] = 0;
next.s[p.k] = p.s[next.k];
next.s[next.k] = 'x';
int hash = permutation_hash(next.s);
if(!vis[hash])
{
vis[hash] = true;
q.push(next);
}
}
}
}
return -1;
}

int main()
{
fact[0] = 1;
for(int i = 1; i < 9; i ++)  fact[i] = fact[i - 1] * i;
char c[2],str[10];
Point start;
for(int i = 0; i < 9; i ++)
{
scanf("%s",&c);
if(c[0] == 'x')
start.k = i;
start.s[i] = c[0];
}
start.s[9] = 0;
start.step = 0;
printf("%d",bfs(start));
return 0;
}



#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int n, m;
#define MAXN 105
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int g[MAXN][MAXN], d[MAXN][MAXN];
int bfs()
{
queue <PII> q;
for(auto &v : d)
for(auto &x : v)
x = - 1;
d[0][0] = 0;
q.push({0, 0});
while (!q.empty())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int x = t.first + dx[i], y = t.second + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
{
d[x][y] = d[t.first][t.second] + 1;
q.push({x, y});
}
}
}
return d[n - 1][m - 1];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define MAXN 25
int n;
char g[MAXN][MAXN];
bool col[MAXN], dg[MAXN], udg[MAXN];
void dfs(int u)
{
if(u == n)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
printf("%c", g[i][j]);
puts("");
}
puts("");
return;
}
for(int i = 0; i < n; i++)
if(!col[i] && !dg[u + i] && !udg[n - u + i])
{
g[u][i] = 'Q';
col[i] = 1;
dg[u + i] = 1;
udg[n - u + i] = 1;
dfs(u + 1);
col[i] = 0;
dg[u + i] = 0;
udg[n - u + i] = false;
g[u][i] = '.';
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
g[i][j] = '.';
dfs(0);
return 0;
}



#include <iostream>
using namespace std;
#define MAXN 15
int n;
int path[MAXN];
bool flag[MAXN];
void dfs(int u)
{
if(u == n)
{
for(int i = 0; i < n; i++)
printf("%d ", path[i]);
puts("");
return;
}
else
{
for(int i = 1; i <= n; i++)
{
if(!flag[i])
{
flag[i] = true;
path[u] = i;
dfs(u + 1);
flag[i] = false;
path[u] = 0;
}
}
}
}
int main()
{
scanf("%d", &n);
dfs(0);
return 0;
}



/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *prev = nullptr;
while (cur)
{
ListNode *next = cur->next;
cur->next = prev;
prev = cur, cur = next;
}
return prev;
}
};



class Solution {
public:
int strToInt(string str) {
int k = 0;
while(k < str.size() && str[k] == ' ')
k++;
bool is_minus = false;
long long num = 0;
if(str[k] == '+') k++;
else if(str[k] == '-') k++, is_minus = true;
while(k < str.size() && str[k] >= '0' && str[k] <= '9')
{
num = num * 10 + str[k] - '0';
k++;
}
if(is_minus)
num *= -1;
if(num > INT_MAX) num = INT_MAX;
if(num < INT_MIN) num = INT_MIN;
return (int) num;
}
};