3287

Colopen

Tilbur
Nottoday
15084948533
sketch
Aaron_8

QAQlzy

utt

yuxi
wslwlm

NBxiang

Hustle

20小时前
import java.util.*;
public class Main {
static int N = 700, M = 100010;

static int ne[] = new int[M], w[] = new int[M], to[] = new int[M], h[] = new int[N], idx;
static double d[] = new double[N];
static int cnt[] = new int[N];
static boolean st[] = new boolean[N];

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

static boolean check(double mid) {
Arrays.fill(cnt, 0);
Arrays.fill(d, 0);
for(int i = 0; i < N; i ++ ) {
st[i] = true;
}

int count = 0;
while(!q.isEmpty()) {
int t = q.poll();
st[t] = false;

for(int i = h[t]; i != -1; i = ne[i]) {
int j = to[i];
if(d[j] < d[t] + w[i] - mid) {
d[j] = d[t] + w[i] - mid;
cnt[j] = cnt[t] + 1;

if( ++ count > 5 * N) return true;
if(cnt[j] >= N) return true;

if(!st[j]) {
st[j] = true;
q.offer(j);
}
}
}
}
return false;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while(n != 0) {
Arrays.fill(h, -1);
idx = 0;
for(int i = 0; i < n; i ++ ) {
char cs[] = sc.next().toCharArray();
int len = cs.length;
int a = (cs[0] - 'a') * 26 + (cs[1] - 'a');
int b = (cs[len - 2] - 'a') * 26 + (cs[len - 1] - 'a');
}

if(!check(0)) System.out.println("No solution");
else {
double l = 0, r = 1000;
while(r - l > 1e-5) {
double mid = (l + r) / 2;
if(check(mid))
l = mid;
else
r = mid;
}
System.out.println(l);
}

n = sc.nextInt();
}
}

}


20小时前
import java.util.*;
public class Main {
static int N = 510, M = 5500;

static int w[] = new int[M], h[] = new int[N], ne[] = new int[M], to[] = new int[M], idx;
static boolean st[] = new boolean[N];
static int dist[] = new int[N], cnt[] = new int[N];
static int n, m1, m2;

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

static boolean spfa() {
for(int i = 1; i <= n; i ++ ) {
q.offer(i);
st[i] = true;
cnt[i] = dist[i] = 0;
}

while(!q.isEmpty()) {
int v = q.poll();
st[v] = false;

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

if(cnt[j] >= n)
return true;

if(!st[j]) {
st[j] = true;
q.offer(j);
}
}
}
}
return false;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();

while(T -- > 0) {
n = sc.nextInt();
m1 = sc.nextInt();
m2 = sc.nextInt();
Arrays.fill(h, -1);
idx = 0;

for(int i = 0; i < m1; i ++ ) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
}
for(int i = 0; i < m2; i ++ ) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
}

String res = spfa() ? "YES" : "NO";
System.out.println(res);
}
}

}


import java.util.*;
public class Main {
static int N = 1010, M = 5010;

static int to[] = new int[M], ne[] = new int[M], h[] = new int[N], w[] = new int[M], idx;
static int cnt[] = new int[N], wf[] = new int[N];
static double dist[] = new double[N];
static boolean st[] = new boolean[N];
static int n, m;

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

static boolean check(double mid) {
Arrays.fill(dist, 0);
Arrays.fill(cnt, 0);
Arrays.fill(st, false);
for(int i = 1; i <= n; i ++ ) {
q.offer(i);
st[i] = true;
}

while(!q.isEmpty()) {
int t = q.poll();
st[t] = false;

for(int i = h[t]; i != -1; i = ne[i]) {
int j = to[i];
if(dist[j] < dist[t] + wf[t] - mid * w[i]) {
dist[j] = dist[t] + wf[t] - mid * w[i];
cnt[j] = cnt[t] + 1;

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

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i = 1; i <= n; i ++ ) wf[i] = sc.nextInt();

Arrays.fill(h, -1);
while(m -- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
}

double l = 0, r = 1010;
while(r - l > 1e-4) {
double mid = (r + l) / 2;
if(check(mid)) l = mid;
else r = mid;
}

System.out.printf("%.2f", l);
}
}


import java.util.*;
public class Main {
static class e implements Comparable<e> {
int a, b, d;
boolean is = false;
public e(int aa, int bb, int cc) {
a = aa; b = bb; d = cc;
}
public int compareTo(e o) {
return this.d - o.d;
}
}

static int N = 510, M = 10010;

static int n, m;
static int p[] = new int[N];
static e es[] = new e[M];
static int max1[][] = new int[N][N], max2[][] = new int[N][N];
static int ne[] = new int[N * 2], to[] = new int[N * 2], w[] = new int[N * 2], h[] = new int[N], idx;

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

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

static void dfs(int u, int m1, int m2, int fa, int cur) {
max1[cur][u] = m1;
max2[cur][u] = m2;

for(int i = h[u]; i != -1; i = ne[i]) {
int j = to[i];
if(j == fa) continue;
int t1 = m1, t2 = m2;
if(w[i] > m1) {
m2 = m1;
m1 = w[i];
}else if(w[i] < m1 && w[i] > m2) {
m2 = w[i];
}
dfs(j, m1, m2, u, cur);
m1 = t1; m2 = t2;
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);

for(int i = 0; i < m; i ++ ) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
es[i] = new e(a, b, c);
}

Arrays.sort(es, 0, m);
for(int i = 1; i <= n; i ++ ) p[i] = i;

long sum = 0;
for(int i = 0; i < m; i ++ ) {
int a = find(es[i].a), b = find(es[i].b);
if(a != b) {
p[a] = b;
sum += es[i].d;
es[i].is = true;
}
}

for(int i = 1; i <= n; i ++ ) {
dfs(i, 0, 0, -1, i);
}

long res = (long)1e18;
for(int i = 0; i < m; i ++ ) {
if(!es[i].is) {
int a = es[i].a, b = es[i].b, w = es[i].d;
if(w > max1[a][b]) {
res = Math.min(res, sum - max1[a][b] + w);
}else if(w == max1[a][b] && w  > max2[a][b]) {
res = Math.min(res, sum - max2[a][b] + w);
}

}
}
System.out.println(res);
}
}


import java.util.*;
public class Main {
static class e implements Comparable<e> {
int a, b, d;
public e(int aa, int bb, int cc) {
a = aa; b = bb; d = cc;
}
public int compareTo(e o) {
return this.d - o.d;
}
}

static int N = 6010;
static e es[] = new e[N];
static int p[] = new int[N], size[] = new int[N];

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

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();

while(T -- > 0) {
int n = sc.nextInt();
for(int i = 0; i < n - 1; i ++ ) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
es[i] = new e(a, b, c);
}

Arrays.sort(es, 0, n - 1);

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

int res = 0;
for(int i = 0; i < n - 1; i ++ ) {
int a = find(es[i].a), b = find(es[i].b), w = es[i].d;
if(a != b) {
res += (size[a] * size[b] - 1) * (w + 1);
p[a] = b;
size[b] += size[a];
}
}

System.out.println(res);
}
}
}


// 16:34
import java.util.*;
public class Main {
static class e implements Comparable<e> {
int a, b;
double d;
public int compareTo(e o) {
return (int)(this.d - o.d);
}
}

static int N = 510;

static e es[] = new e[N * N];
static int xs[] = new int[N], ys[] = new int[N];
static int p[] = new int[N];
static int n, k;

static int init() {
int t = 0;
for(int i = 1; i <= n; i ++ )
for(int j = i + 1; j <= n; j ++ , t ++ ) {
es[t] = new e();
es[t].a = i; es[t].b = j; es[t].d = get(i, j);
}
return t;
}

static double get(int a, int b) {
double t1 = xs[a] - xs[b];
double t2 = ys[a] - ys[b];
return Math.sqrt(t1 * t1 + t2 * t2);
}

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

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();

for(int i = 1; i <= n; i ++ ) {
int a = sc.nextInt();
int b = sc.nextInt();
xs[i] = a; ys[i] = b;
p[i] = i;
}

int m = init();
Arrays.sort(es, 0, m);

int liantong = n;
double res = 0;
for(int i = 0; i < m && liantong > k; i ++ ) {
int a = find(es[i].a);
int b = find(es[i].b);
if(a != b) {
res = es[i].d;
liantong -- ;
p[a] = b;
}
}

System.out.printf("%.2f",res);
}
}


import java.util.*;
public class Main {
static int N = 310;

static int g[][] = new int[N][N];
static int d[] = new int[N];
static boolean st[] = new boolean[N];
static int n;

static int prim() {
Arrays.fill(d, 10000000);
int res = 0;

for(int i = 0; i <= n; i ++ ) {
int t = -1;
for(int j = 0; j <= n; j ++ )
if(!st[j] && (t == -1 || d[j] < d[t]))
t = j;

st[t] = true;
if(i != 0) res += d[t];

for(int j = 0; j <= n; j ++ )
d[j] = Math.min(d[j], g[j][t]);
}
return res;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

n = sc.nextInt();
for(int i = 1; i <= n; i ++ ) {
g[i][0] = sc.nextInt();
g[0][i] = g[i][0];
}
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
g[i][j] = sc.nextInt();

System.out.println(prim());
}
}



import java.util.*;
public class Main {
static class e {
int a, b, d;
public e(int aa, int bb, int cc) {
a = aa; b = bb; d = cc;
}
}

static int N = 1010;

static int p[] = new int[N * N];
static int ids[][] = new int[N][N];
static e es[] = new e[2 * N * N];
static int n, m;

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

static int get_edges() {
int cnt = 0;
for(int j = 1; j <= m; j ++ ) {
for(int i = 1; i <= n - 1; i ++ ) {
int a = ids[i][j], b = ids[i + 1][j];
es[cnt ++ ] = new e(a, b, 1);
}
}

for(int i = 1; i <= n; i ++ ) {
for(int j = 1; j <= m - 1; j ++ ) {
int a = ids[i][j], b = ids[i][j + 1];
es[cnt ++ ] = new e(a, b, 2);
}
}
return cnt;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();

for(int i = 1, t = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ ) {
ids[i][j] = t ++ ;
}

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

while(sc.hasNext()) {
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
int a = ids[x1][y1], b = ids[x2][y2];
p[find(a)] = find(b);
}

int res = 0;
int cnt = get_edges();
for(int i = 0; i < cnt; i ++ ) {
int a = find(es[i].a);
int b = find(es[i].b);
if(a != b) {
p[a] = b;
res += es[i].d;
}
}

System.out.println(res);
}

}


import java.util.*;
public class Main {
static class e implements Comparable<e> {
int a, b, d;
public e(int aa, int bb, int cc) {
a = aa; b = bb; d = cc;
}
public int compareTo(e o) {
return this.d - o.d;
}
}

static int N = 2010, M = 10010;

static int p[] = new int[N];
static e es[] = new e[M];
static int n, m;

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

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int q = 0, res = 0;

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

for(int i = 0; i < m; i ++ ) {
int pp = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
if(pp == 1) {
a = find(a); b = find(b);
p[a] = b;
res += c;
}else
es[q ++ ] = new e(a, b, c);
}

Arrays.sort(es, 0, q);

for(int i = 0; i < q; i ++ ) {
int a = find(es[i].a);
int b = find(es[i].b);

if(a != b) {
p[a] = b;
res += es[i].d;
}
}

System.out.println(res);
}

}


import java.util.*;
public class Main {
static class e implements Comparable<e> {
int d, a, b;
public e(int aa, int bb, int cc) {
a = aa; b = bb; d = cc;
}
public int compareTo(e o){
return this.d - o.d;
}
}

static int N = 310;

static e es[] = new e[9000];
static int n, m;
static int p[] = new int[N];

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

static boolean check(int x) {
for(int i = 1; i <= n; i ++ )
p[i] = i;

int sum = 0;
for(int i = 0; i < m; i ++ ) {
int a = es[i].a;
int b = es[i].b;
int d = es[i].d;

if(d > x) break;

a = find(a); b = find(b);
if(a != b) {
p[a] = b;
sum ++ ;
}
}

return sum == n - 1;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();

for(int i = 0; i < m; i ++ ) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
es[i] = new e(a, b, c);
}

Arrays.sort(es, 0, m);

int l = 1, r = 10000;
while(l < r) {
int mid = l + r >> 1;
if(check(mid))
r = mid;
else
l = mid + 1;
}
System.out.println(n - 1 + " " + l);
}

}