274

thejohn

dp_5

yxc

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

const int N = 510, M = 1e5 + 10;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];//match表示女生节点匹配的男生节点是什么
bool st[N];//st表示女生节点是否被预定

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool find(int x)
{
for(int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
//如果当前j女生未被预定，如果被预定了，帮与她匹配的男生节点match[j]找其他可匹配的女生
if(match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}
//找不到能匹配的女生
return false;
}

int main()
{
scanf("%d%d%d", &n1, &n2, &m);
memset(h, -1, sizeof h);
while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
}

int res = 0;
//遍历所有男生节点
for(int i = 1; i <= n1; i++)
{
memset(st, false, sizeof st);
if(find(i)) res ++;
}
printf("%d", res);
return 0;
}


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

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

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int c)
{
color[u] = c;
//遍历与当前节点连接的节点
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!color[j])
{
if(!dfs(j, 3 - c)) return false;//将下一节点染上与当前节点不同颜色
}
//如果下一节点与当前节点颜色相同
else if (color[j] == c) return false;
}
return true;
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1 , sizeof h);

while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
}

bool flag = true;
//遍历每个点
for(int i = 1; i <= n; i++)
if(!color[i])
{
if(!dfs(i, 1))
{
flag = false;
break;
}
}

if(flag) puts("Yes");
else puts("No");

return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int p[N];//存储父节点

struct Edge
{
int a, b, w;

bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];

int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}

int kruskal()
{
sort(edges, edges + m);

for(int i = 1; i <= n; i++) p[i] = i;

int res = 0, cnt = 0;
for(int i = 0; i < m; i++)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;

a = find(a), b = find(b);
if(a != b)
{
p[a] = b;
res += w;
cnt ++;
}
}
if(cnt < n - 1) return INF;
return res;
}

int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}

int t = kruskal();

if(t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}


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

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;
for(int i = 0; i < n ; i++)
{
int t = -1;
for(int j = 1; j <= n; j ++)
{
//找到与集合最近的点
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
if(i && dist[t] == INF) return INF;
if(i) res += dist[t];
st[t] = true;
//更新集合外的点，到集合的最小距离
for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
}
return res;
}

int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);

while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if(t == INF) puts("impossible");
else printf("%d", t);

return 0;
}


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

const int N = 1e5 + 10;

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

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort()
{
int hh = 0, tt = -1;
for(int i = 1; i <= n; i++)
if(!d[i])
q[++ tt] = i;

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

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--)
{
int a, b;
cin >> a >> b;
//d[i]代表每个点的入度
d[b] ++;
}
if(!topsort()) puts("-1");
else
{
for(int i = 0; i < n; i ++) printf("%d ", q[i]);
}
return 0;
}


#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5 + 10;

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

void add(int a, int b)
{
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()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
}

printf("%d", bfs());
return 0;
}


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

using namespace std;

const int N = 1e5 + 10;

int n;
int h[N], e[N * 2], ne[N * 2], idx;
bool st[N];
int ans = N;

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
st[u] = true;
int size = 0, sum = 1;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(st[j]) continue;

int s = dfs(j);//返回的是以u为根的子树，除u外的节点数之和
size = max(size, s);//记录连通子图的最大节点数
//sum记录u为根的子树的节点和。包括u，因为要挖掉u
sum += s;
}
//将u为根的子树，挖掉u后最大 连通子图的节点数size，与去掉u为根的这个子树之后，
//剩余节点数比较。样例，u=4时，4的父亲节点，并且其他与之相连的节点总数就是n - sum。
size = max(size, n - sum);
//每一次遍历都比较剩余连通子图的最大节点数，取最小。
ans = min(ans, size);
return sum;
}

int main()
{
scanf("%d", &n);
memset(h, -1 , sizeof h);
for(int i = 0; i < n - 1; i++)
{
int a, b;
scanf("%d%d", &a, &b);
}

dfs(1);

printf("%d", ans);
return 0;
}


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

using namespace std;

const int N = 1e5 + 10;

int n;
int h[N], e[N * 2], ne[N * 2], idx;
bool st[N];
int ans = N;

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
st[u] = true;
int size = 0, sum = 0;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(st[j]) continue;

int s = dfs(j);
size = max(size, s);
sum += s;
}

size = max(size, n - sum - 1);
ans = min(ans, size);
return sum + 1;
}

int main()
{
scanf("%d", &n);
memset(h, -1 , sizeof h);
for(int i = 0; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
}

dfs(1);

printf("%d", ans);
return 0;
}


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

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

//从任意的i到任意的j，最短路径有两种情况
//1、i直接到j
//2、i经过若干的点到j
//即式子d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
//一眼看去，感觉只是多考虑的一个点k，i->k,k->j是不是比i->j短，但展开看就发现，其实是考虑了1到k-1的节点总和
//有4个点，1,2,3,4;当k=3 d[1][4] = min(d[1][4], d[1][3] + d[3][4]),
//d[1][3]可能是d[1][2] + d[2][3], d[1][4] = min(d[1][4], d[1][2] + d[2][3] + d[3][4])
//例子只供理解思路，不是真实例子。
void floyd()
{
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
scanf("%d%d%d", &n, &m, &Q);
//初始化
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF;

while(m --)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
d[a][b] = min(d[a][b], w);
}

floyd();

while(Q --)
{
int a, b;
scanf("%d%d", &a, &b);
int t = d[a][b];
if(t > INF / 2) puts("impossible");
else printf("%d\n", t);
}
return 0;
}


#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
queue<int> q;

//这里dist不初始化，随便什么值都可以，现在dist[]的值是0，只有碰到负权边才会更新，开始记录cnt。
//有dist这个前提在，如果负环在源节点无法到达的地方，那么可能无法从源节点更新到负环。
//因此需要把每个点都先放入队列，以免从初始节点开始就结束了，找不到后面的点。
//如样例所示，如果不把每个点都放入队列，dist[2]不会更新，也就无法遍历到2->3的负权边。
for(int i = 1; i <= n; i++)
{
st[i] = true;
q.push(i);
}

while(q.size())
{
int t = q.front();
q.pop();

st[t] = false;

for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;

if(cnt[j] >= n) return true;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}

int main()
{
scanf("%d%d", &n, &m);

memset(h, -1, sizeof h);

while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);