2021,10,18 题解报告

2021,10,18 题解报告

写在前面

\(T1\)没想出来，卒

T1

招待（entertain）

题目

solution

对\(W\)进行三进制拆分，每一位是一个砝码。

如果第\(i\)位是\(2\) 就将其进位（在该位置放一个物品),因为每个物品只有一个。

最后得到的一个\(01\) 串就是放物品的最终状态。

code

/*

爱丽儿：上班

知识：

时间：

*/

#包括牡蛎

#includecstdio

# includecstring

#包括

#包括算法

#定义整数长

使用命名空间标准；

int read(){ 0

int x=0，f=1；char c=getchar()；

while(c ‘ 0 ‘ | | c ‘ 9 ‘){ if(c==’-‘)f=-1；c=getchar()；}

while(c=’ 0 ‘ c=’ 9 ‘){ x=x * 10 c-‘ 0 ‘；c=getchar()；}

返回x * f；

}

int stc[200]，sc，a[200]，b[200]，W，x；

签名main(){ 0

b[1]=1；

for(int I=2；I=35I)b[I]=b[I-1]* 3；

w=read()；

x=W；

while(x) {stc[ sc]=x % 3，x/=3；}

for(int I=1；i=scI){ 0

STC[I 1]=STC[I/3]；

STC[I]%=3；

if(STC[I]==2){ 0

stc[i 1]，STC[I]=0；

a[i]=真；

}

if(stc[i 1] 0) sc=max(i 1，sc)；

}

for(int I=1；I=ScI)if(STC[I]==1)coutb[I]’ ‘；

puts(‘ ‘)；

coutW

for(int I=1；I=ScI)if(a[I])coutb[I]’ ‘；

puts(‘ ‘)；

返回0;

}

T2

novel

题目

solution

数据范围不大，分层图直接碾过去了==。

正解是二分路径的最大值，然后\(bfs\)判断是否合法。

code

/*

爱丽儿：上班

知识：

时间：

*/

#包括牡蛎

#includecstdio

# includecstring

#包括

#包括算法

使用命名空间标准；

const int MAXN=1e5 5

const int MAXM=2e5 5

int read(){ 0

int x=0，f=1；char c=getchar()；

while(c ‘ 0 ‘ | | c ‘ 9 ‘){ if(c==’-‘)f=-1；c=getchar()；}

while(c=’ 0 ‘ c=’ 9 ‘){ x=x * 10 c-‘ 0 ‘；c=getchar()；}

返回x * f；

}

int n，m，k，fa[MAXN]，Ans=0x3f3f3f

结构边缘{int v，nxt，w；} e[MAXM 1]；

int head[MAXN]，E；

void add_edge(int u，int v，int w){ 0

e[ E]=(边){v，头[u]，w }；

头[u]=E；

}

int find(int x){ 0

返回fa[x]==x x : fa[x]=find(fa[x])；

}

queueint q；

int dis[MAXN]；

无效工作(int ){ 0

memset(dis，0x3f，sizeof dis)；

dis[s]=0，q . push

while(！q . empty()){ 0

int u=q . front()；q . pop()；

for(int I=head[u]；我；我

= e[i].nxt) {
int v = e[i].v;
if(dis[v] max(dis[u], e[i].w)) {
dis[v] = max(dis[u], e[i].w);
if(v % n != 0) q.push(v);
}
}
}
}
int main(){
freopen(“novel.in”, “r”, stdin);
freopen(“novel.out”, “w”, stdout);
n = read(), m = read(), k = read();
for (int i = 1; i = n; i++) fa[i] = i;
for (int i = 1; i = m; i++) {
int u = read(), v = read(), w = read();
add_edge(u, v, w), add_edge(v, u, w);
for (int j = 1; j = k; j++){
add_edge(u + (j – 1) * n, v + j * n, 0);
add_edge(v + (j – 1) * n, u + j * n, 0);
add_edge(u + j * n, v + j * n, w);
add_edge(v + j * n, u + j * n, w);
}
if(find(u) != find(v)) fa[find(u)] = find(v);
}
if(find(1) != find(n)) {puts(“-1”); return 0;}
work(1);
for(int i = 0; i = k; i++) Ans = min(Ans, dis[n + n * k]);
coutAns;
return 0;
}

chen_怡’s code

二分

code

#includeiostream
#includecstdio
#includecstring
#includequeue
#includestack
#includealgorithm
#includemap
#define int long long 
using namespace std;
const int N = 1e3 + 9;
const int M = 1e4 + 9;
struct node{
	int last;
	int to;
	int dis;
}e[M1];
int n , m , k;
int dis[N];
int head[N] , cnt;
bool vis[N];
int l = 0 , r = 0;
int ans = -1;
int read()
{
	int f = 1 , x = 0;
	char s = getchar();
	while(s'0' || s'9'){if(s=='-')f=-1;s=getchar();}
	while(s='0's='9'){x=(x1)+(x3)+(s^'0');s=getchar(); }
	return f*x;
} 
void add(int from,int to,int dis)
{
	e[++cnt].last = head[from];
	e[cnt].to = to;
	e[cnt].dis = dis;
	head[from] = cnt;
}
bool check(int x)
{
	queueint q;
	memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[1] = 0;
	q.push(1);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i = head[u] ; i ; i = e[i].last)
		{
			int v = e[i].to;
			int w = e[i].dis;
			if(w = x)
			{
				if(dis[v]  dis[u])
				{
					dis[v] = dis[u];
					if(!vis[v])
					{
						q.push(v);
						vis[v] = true;
					}
				}
			}
			else if(w  x and dis[u]  k)
			{
				if(dis[v]  dis[u] + 1)
				{
					dis[v] = dis[u] + 1;
					if(!vis[v])
					{
						q.push(v);
						vis[v] = true;	
					}
				}
			}
		}
	}
	return dis[n] = k;
}
signed main()
{
	n = read(); m = read();
	k = read();
	for(int i = 1 ; i = m ; i ++)
	{
		int u = read();
		int v = read();
		int w = read();
		add(u,v,w);
		add(v,u,w);
		r = max(r , w);
	}
	while(l = r)
	{
		int mid = (l + r) 1;
		if(check(mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	printf("%lld\n",ans);
	return 0;
}

T3

solution

在 \([?100,100]\) 中二分得到 \(mid\)，让所有红叶的年轻程度加上该 \(mid\) 值，跑 \(Kruskal\)，直到得到最终结果;

发现修改权值之后会有重复的部分。

这个可以直接在排序的时候把红色的边放到前面就好了。

code

/*
work by: Ariel_
Knowledge:
Time:
*/
#includeiostream
#includecstdio
#includecstring
#includequeue
#includealgorithm
#define int long long
using namespace std;
const int MAXN = 500005;
const int MAXM = 100005;
int read() {
  int x = 0, f = 1; char c = getchar();
  while(c  '0' || c  '9') {if(c == '-') f = -1;c = getchar();}
  while(c = '0'  c = '9') {x = x * 10 + c - '0';c = getchar();}
  return x * f;
}
struct edge{
    int w, cw, u, v, col;
    bool operator  (const edge rhs) const {
    	if(cw == rhs.cw) return col  rhs.col;
    	return cw  rhs.cw;
    }
}e[MAXM];
int fa[MAXN], n, m, need;
int find(int x) {return fa[x] == x  fa[x] : fa[x] = find(fa[x]);}
int kruskal(int x) {
    int cnt = 0, ret = 0;
    for(int i = 1; i = n; i++) fa[i] = i;
    for(int i = 1; i = m; i++){
        if(!e[i].col) e[i].cw = e[i].w + x;
        else e[i].cw = e[i].w;
    }
    sort(e + 1, e + m + 1);
    for(int i = 1; i = m; i++){
        if(find(e[i].u) != find(e[i].v)){
            fa[find(e[i].u)] = find(e[i].v);
            if(!e[i].col) cnt++;
            ret += e[i].cw;
        }
    }
    return cnt = need  ret : -1;
}
int work(int l, int r) {
    if(l == r) return l;
    int mid = (l + r + 1)  1;
    int x = kruskal(mid);
    if(x == -1) return work(l, mid - 1);
    return work(mid, r);
}
signed main() {
    n = read(), m = read(), need = read();
    for(int i = 1; i = m; i++){
      e[i].u = read() + 1, e[i].v = read() + 1;
	  e[i].w = read(), e[i].col = read();
    }
    int k = work(-500, 500);
    printf("%lld\n", kruskal(k) - need * k);
    return 0;
}