图论练习3

内容：过程中视条件改变边权，利用树状数组区间加处理

卯酉东海道

题目链接

题目大意

$n$ 个点， $m$ 条有向边，每条边有颜色 $c_i$ 和费用 $w_i$
总共有 $l$ 种颜色
若当前颜色与要走的边颜色相同，则花费为 $w_i$
若当前颜色与要走的边颜色不同，则花费为 $base*w_i$ ，且颜色变为边的颜色
出发时可以自定义颜色
问 $1\rightarrow n$ 的最小花费

解题思路

选边 $u\rightarrow v$ 时，进行判断 $\left\{\begin{matrix} if\ c_u=c_{w(u,v)} &w(u,v)=w \\ else& w(u,v)=w*base,c_v=c_{w(u,v)} \end{matrix}\right.$
对于初始自定义颜色，且 $1\leq l\leq 64$ ，则跑 $l$ 趟最短路

import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;public class Main{staticclass Node{int id;int col;long dis;public Node(int I,int C,long D) {id=I;col=C;dis=D;}}static int cnt=0;static int[] head;static Edge[] e;staticclass Edge{int fr;int to;int nxt;long val;int col;}static void addEdge(int fr,int to,long val,int col) {cnt++;e[cnt]=new Edge();e[cnt].fr=fr;e[cnt].to=to;e[cnt].val=val;e[cnt].nxt=head[fr];e[cnt].col=col;head[fr]=cnt;}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int n=input.nextInt();int m=input.nextInt();int l=input.nextInt();int base=input.nextInt();e=new Edge[m<<1|1];head=new int[n+1];for(int i=1;i<=m;++i) {int u=input.nextInt();int v=input.nextInt();int col=input.nextInt();long w=input.nextLong();addEdge(u, v, w,col);	}PriorityQueue<Node> que=new PriorityQueue<Node>((o1,o2)->{if(o1.dis-o2.dis>0)return 1;else if(o1.dis-o2.dis<0)return -1;else return 0;});boolean[] vis=new boolean[n+1];long[] dis=new long[n+1];long ans=Long.MAX_VALUE;for(int o=1;o<=l;++o) {Node s=new Node(1,o,0);Arrays.fill(vis, false);Arrays.fill(dis, Long.MAX_VALUE);dis[1]=0;que.add(s);while(!que.isEmpty()) {Node now=que.peek();que.poll();int u=now.id;if(vis[u])continue;long disu=now.dis;int colu=now.col;vis[u]=true;for(int i=head[u];i>0;i=e[i].nxt) {int v=e[i].to;int colv=e[i].col;long w=e[i].val;if(colv!=colu) {w=base*w;}if(dis[v]>disu+w) {dis[v]=disu+w;que.add(new Node(v, colv, dis[v]));}}}ans=Math.min(ans, dis[n]);}if(ans==Long.MAX_VALUE) {out.println(-1);}else {out.println(ans);}out.flush();out.close();}staticclass AReader{BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}

AtCoder abc338 D - Island Tour

题目链接

题目大意

$n$ 个点， $n$ 条无向边依次连接，第 $n$ 条连接 $n\rightleftharpoons 1$
给定序列 $x_1,x_2\cdots x_k$ ，从 $x_1$ 依次访问
$x_i\rightarrow x_j$ 的路径长度，定义为经过的边的个数
问删除一条边后，完成访问的最短路径长度

解题思路

先不管删边
$u\rightarrow v$ 有两种方式，一种绕一圈，一种直接顺着走
两种方式种的较小值加入答案
但是有删边，所以删去边后可能导致取到较小值的路径无法通过，需要撤回，改为另一种
若删除这条边，则通过它的所有较小值均要改变，即加上差值
由于边标号连续，考虑树状数组区间加
对于当前较小值经过的所有边，加上差值，作为撤回代价
在不考虑删边的情况下统计完答案后，单点查询每条边，取撤回代价最小的边为删边
$\left\{\begin{matrix} x_i<x_j &one:x_j-x_i&two:(n-x_j+1)+(x_i-1) \\ x_i>x_j & one :x_i-x_j&two:(n-x_i+1)+(x_j-1) \end{matrix}\right.$

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;public class Main{static int cnt=0;static int[] head;staticclass Edge{int fr;int to;int nxt;long val;}static Edge[] e;static void addEdge(int fr,int to,long val) {cnt++;e[cnt]=new Edge();e[cnt].fr=fr;e[cnt].to=to;e[cnt].nxt=head[fr];head[fr]=cnt;}staticclass Node{int x;long dis;long h;public Node(int X,long D,long H) {x=X;dis=D;h=H;}}staticclass BIT{int size;long[] tr;public BIT(int n) {size=n;tr=new long[n+2];}public int lowbit(int x) {return x&(-x);}public void update(int x,long y) {for(int i=x;i<=size;i+=lowbit(i)) {tr[i]+=y;}}public long query(int x) {long res=0;for(int i=x;i>0;i-=lowbit(i)) {res+=tr[i];}return res;}}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int n=input.nextInt();int m=input.nextInt();BIT Tree=new BIT(n);int[] X=new int[m+1];for(int i=1;i<=m;++i) {X[i]=input.nextInt();}long ans=0;for(int i=1;i<m;++i) {int x=X[i];int y=X[i+1];if(x==y)continue;long tol;long tor;long cha;if(x<y) {tol=(n+x-y);tor=(y-x);if(tol>tor) {ans+=tor;cha=tol-tor;Tree.update(x, cha);Tree.update(y, -cha);}else {ans+=tol;cha=tor-tol;Tree.update(1, cha);Tree.update(x,-cha);Tree.update(y, cha);Tree.update(n+1, -cha);}}else {tol=x-y;tor=n-x+y;if(tol>tor) {ans+=tor;cha=tol-tor;Tree.update(x, cha);Tree.update(n+1,-cha);Tree.update(1, cha);Tree.update(y, -cha);}else {ans+=tol;cha=tor-tol;Tree.update(y, cha);Tree.update(x, -cha);}}}long shan=Long.MAX_VALUE/2;for(int i=1;i<=n;++i) {shan=Math.min(shan, Tree.query(i));}
//	    out.println(ans);out.println(ans+shan);out.flush();out.close();}staticclass AReader {private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer = new StringTokenizer("");private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine = innerNextLine();if (nextLine == null) {return false;}tokenizer = new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer = new StringTokenizer("");return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}}
}

AtCoder abc338 E - Chords

题目链接

题目大意

在一个圆上等距离放置了 $2n$ 个点，从某个点开始顺时针编号为 $1$ 到 $2n$
同时在圆上有 $n$ 条弦，第i条弦连接点 $A_i$ 和 $B_i$ 。保证所有的 $A_i,B_i,(i=1,2,\cdots n)$ 不同
判断这些弦是否有交

解题思路

集合划分
若两个不同集合之间有弦，则有交
由于点标号连续，对于每个弦，考虑树状数组区间加
$A_i\rightarrow B_i$ 之间的点，区间加 $1$ ，表示一个新集合
端点无所谓，反正保证所有的 $A_i,B_i,(i=1,2,\cdots n)$ 不同
若 $query(A_i)\neq query(B_i)$ ，则 $A_i,B_i$ 不在一个集合且有弦，满足有交

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;public class Main{static int cnt=0;static int[] head;staticclass Edge{int fr;int to;int nxt;long val;}static Edge[] e;static void addEdge(int fr,int to,long val) {cnt++;e[cnt]=new Edge();e[cnt].fr=fr;e[cnt].to=to;e[cnt].nxt=head[fr];head[fr]=cnt;}staticclass Node{int x;long dis;long h;public Node(int X,long D,long H) {x=X;dis=D;h=H;}}staticclass BIT{int size;long[] tr;public BIT(int n) {size=n;tr=new long[n+2];}public int lowbit(int x) {return x&(-x);}public void update(int x,long y) {for(int i=x;i<=size;i+=lowbit(i)) {tr[i]+=y;}}public long query(int x) {long res=0;for(int i=x;i>0;i-=lowbit(i)) {res+=tr[i];}return res;}}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int n=input.nextInt();BIT Tree=new BIT(2*n);boolean ok=true;for(int i=1;i<=n;++i) {int x=input.nextInt();int y=input.nextInt();if(x>y) {int t=x;x=y;y=t;}if(!ok)continue;long fx=Tree.query(x);long fy=Tree.query(y);if(fx!=fy) {ok=false;}else {Tree.update(x, 1);Tree.update(y, -1);}}if(ok) {out.println("No");}else {out.println("Yes");}out.flush();out.close();}staticclass AReader {private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));private StringTokenizer tokenizer = new StringTokenizer("");private String innerNextLine() {try {return reader.readLine();} catch (IOException ex) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String nextLine = innerNextLine();if (nextLine == null) {return false;}tokenizer = new StringTokenizer(nextLine);}return true;}public String nextLine() {tokenizer = new StringTokenizer("");return innerNextLine();}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}}
}