图论练习2

内容：路径计数DP，差分约束

最短路计数

题目大意

给一个 $n$ 个点 $m$ 条边的无向无权图，问从 $1$ 出发到其他每个点的最短路有多少条
有自环和重边，对答案 $mod100003$

解题思路

设边权为1，跑最短路
$\left\{\begin{matrix} if\ dis_v>dis_u+w(u,v) & tot_v=tot_u\\ if \ dis_v=dis_u+w(u,v) &tot_v+=tot_u \end{matrix}\right.$
$tot_u$ 表示 $1\rightarrow u$ 的路径数
自环和重边不影响最短路


import java.io.*;
import java.math.BigInteger;
import java.util.PriorityQueue;
import java.util.StringTokenizer;public class Main{static long mod=100003;static long inf=Long.MAX_VALUE/2;static Edge[] e;static int[] head;static int cnt;staticclass Edge{int fr,to,nxt;long val;public Edge(int u,int v,long w) {fr=u;to=v;val=w;}}static void addEdge(int fr,int to,long val) {cnt++;e[cnt]=new Edge(fr, to, val);e[cnt].nxt=head[fr];head[fr]=cnt;}staticclass Node{int x;long dis;public Node(int X,long D) {x=X;dis=D;}}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();e=new Edge[m<<1|1];head=new int[n+1];long[] dis=new long[n+1];long[] tot=new long[n+1];boolean[] vis=new boolean[n+1];for(int i=1;i<=m;++i) {int u=input.nextInt();int v=input.nextInt();addEdge(u, v, 1);addEdge(v, u, 1);}for(int i=1;i<=n;++i)dis[i]=inf;PriorityQueue<Node> q=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;});dis[1]=0;tot[1]=1;q.add(new Node(1, 0));while(!q.isEmpty()) {Node now=q.peek();q.poll();int x=now.x;if(vis[x])continue;vis[x]=true;long disu=now.dis;for(int i=head[x];i>0;i=e[i].nxt) {int v=e[i].to;long w=e[i].val;if(vis[v])continue;if(dis[v]>disu+w) {dis[v]=disu+w;tot[v]=tot[x];q.add(new Node(v, dis[v]));}else if(dis[v]==disu+w) {tot[v]=(tot[x]+tot[v])%mod;}}}for(int i=1;i<=n;++i) {out.println(tot[i]);}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();}}
}

[HAOI2012]ROAD

题目链接

题目大意

$n$ 个点 $m$ 条单向有权边，对每条边求有多少条最短路经过该边
答案取模1000000007

解题思路

对每个点，求从该点出发到其他点的最短路，将用到的边保留生成新图，其余边无用
对于在新图上的每个点
利用 $Tuopu$ 求从这个点进入的路径数 $a$ ，正着累加
利用 $dfs$ 求从这个点出去的路径数 $b$ ，倒着累加
对于边 $u\rightarrow v$ ， $Num_{u\rightarrow v}+=a_u*b_v\%mod$


import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;public class Main{static int n;static int m;static long inf=Long.MAX_VALUE/2;static long mod=1000000007;staticclass Map{public Map() {cnt=0;head=new int[n+1];e=new Edge[m+1];dis=new long[n+1];vis=new boolean[n+1];}int cnt;int[] head;staticclass Edge{int fr,to,nxt;long val;public Edge(int u,int v,long w) {fr=u;to=v;val=w;}}Edge[] e;void addEdge(int fr,int to,long val) {cnt++;e[cnt]=new Edge(fr, to, val);e[cnt].nxt=head[fr];head[fr]=cnt;}staticclass Node{int x;long dis;public Node(int X,long D) {x=X;dis=D;}}long[] dis;boolean[] vis;void Dij(int s) {for(int i=1;i<=n;++i) dis[i]=inf;for(int i=1;i<=n;++i) vis[i]=false;PriorityQueue<Node> q=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;});dis[s]=0;q.add(new Node(s, 0));while(!q.isEmpty()) {Node now=q.peek();q.poll();int x=now.x;if(vis[x])continue;long disu=now.dis;vis[x]=true;for(int i=head[x];i>0;i=e[i].nxt){int v=e[i].to;long w=e[i].val;if(vis[v])continue;if(disu+w<dis[v]) {dis[v]=disu+w;q.add(new Node(v,dis[v]));}}}}void Make_Tp() {for(int i=1;i<=cnt;++i) {int u=e[i].fr;int v=e[i].to;long w=e[i].val;if(dis[u]+w==dis[v]) {Tp.addEdge(u, v, w, i);Tp.in[v]++;}}}}staticclass Mapp {public Mapp() {cnt=0;head=new int[n+1];e=new Edge[m+1];in=new int[n+1];a=new long[n+1];b=new long[n+1];}int cnt;int[] head;staticclass Edge{int fr,to,nxt,id;long val;public Edge(int u,int v,long w) {fr=u;to=v;val=w;}}Edge[] e;void addEdge(int fr,int to,long val,int id) {cnt++;e[cnt]=new Edge(fr, to, val);e[cnt].id=id;e[cnt].nxt=head[fr];head[fr]=cnt;}int[] in;//s->i--j<-tlong[] a;  long[] b;void stoi(int s) {Queue<Integer> q=new LinkedList<Integer>();q.add(s);a[s]=1;while(!q.isEmpty()) {int u=q.peek();q.poll();for(int i=head[u];i>0;i=e[i].nxt) {int v=e[i].to;a[v]=(a[v]+a[u])%mod;in[v]--;if(in[v]==0)q.add(v);}}}void jfrt(int u) {//不用建反图跑拓扑if(b[u]!=0)return;for(int i=head[u];i>0;i=e[i].nxt) {int v=e[i].to;jfrt(v);b[u]=(b[u]+b[v])%mod;}b[u]++;//j<-j也算}void getf() {for(int i=1;i<=cnt;++i) {int id=e[i].id;int u=e[i].fr;int v=e[i].to;f[id]=(f[id]+a[u]*b[v]%mod)%mod;}}void clear() {cnt=0;Arrays.fill(head, 0);Arrays.fill(in, 0);Arrays.fill(a, 0);Arrays.fill(b, 0);}}static Map T;static Mapp Tp;static long[] f;static void get(int s) {T.Dij(s);Tp.clear();T.Make_Tp();Tp.stoi(s);Tp.jfrt(s);Tp.getf();}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));n=input.nextInt();m=input.nextInt();T=new Map();Tp=new Mapp();f=new long[m+1];for(int i=1;i<=m;++i) {int u=input.nextInt();int v=input.nextInt();long w=input.nextLong();T.addEdge(u, v, w);}for(int i=1;i<=n;++i) get(i);for(int i=1;i<=m;++i)out.println(f[i]);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();}}
}

逛公园

题目链接

题目大意

给一个 $n$ 个点 $m$ 条边构成的有向带权图，没有自环和重边
设 $1\rightarrow n$ 的最短路长为 $d$ ，求 $1\rightarrow n$ 有多少条长度 $\left [ d,d+k \right ]$ 的路径

解题思路

求从 $1$ 出发的最短路， $1\rightarrow u=d_u$
$f[u][x]$ 表示 $1\rightarrow u=d_u+x,x\leq k$ ，路径个数
$u\rightarrow v\Rightarrow d_u+x+w(u,v)=d_v+y,y\leq k$
$x=d_v-d_u-w(u,v)+y$
$f[v][y]+=f[u][x]$
所以反向建图， $dfs(n,y),y\in [0,k]$
若最短路上有0环，则会有无穷多路径
若在 $dfs$ 中，该 $f[v][y]$ 还在等待递归返回答案时，再次被访问，则有0环
初始 $dfs(1,0)$ ，判断 $1$ 在不在0环内，在则 $f[1][0]=\infty$ ，有0环，反之， $f[1][0]=1$


import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static int inf=Integer.MAX_VALUE/2;static int md;staticclass Node{int x;int dis;public Node(int X,int D) {x=X;dis=D;}}staticclass Edge{int fr,to,nxt;int val;public Edge(int u,int v,int w) {fr=u;to=v;val=w;}}staticclass Map{Edge[] e;int[] head;int cnt;public Map(int n,int m) {e=new Edge[m<<1|1];head=new int[n+1];cnt=0;}void addEdge(int fr,int to,int val) {cnt++;e[cnt]=new Edge(fr, to, val);e[cnt].nxt=head[fr];head[fr]=cnt;}}static boolean fail=false;static Map T;static Map Tp;static int[] dis;static long[][] f;static boolean[][] inqu;static void dfs(int v,int k) {//disu+x+w(u,v)=disv+k//x=disv-disu-w+kif(fail)return;if(inqu[v][k]) {//这个状态还没处理又绕回来了，k不变，即走了0环fail=true;return;}if(f[v][k]>0)return;inqu[v][k]=true;long res=0;for(int i=Tp.head[v];i>0;i=Tp.e[i].nxt) {int u=Tp.e[i].to;int w=Tp.e[i].val;int x=dis[v]-dis[u]-w+k;if(x<0)continue;dfs(u, x);res=(res+f[u][x])%md;if(fail)return;}f[v][k]=res;inqu[v][k]=false;}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int O=input.nextInt();while(O>0) {int n=input.nextInt();int m=input.nextInt();int k=input.nextInt();md=input.nextInt();fail=false;T=new Map(n, m);Tp=new Map(n, m);f=new long[n+1][k+1];dis=new int[n+1];inqu=new boolean[n+1][k+1];boolean[] vis=new boolean[n+1];for(int i=1;i<=m;++i) {int u=input.nextInt();int v=input.nextInt();int w=input.nextInt();T.addEdge(u, v, w);Tp.addEdge(v, u, w);}for(int i=1;i<=n;++i)dis[i]=inf;PriorityQueue<Node> q=new PriorityQueue<Node>((o1,o2)->{return o1.dis-o2.dis;});dis[1]=0;q.add(new Node(1, 0));while(!q.isEmpty()) {Node now=q.peek();q.poll();int x=now.x;if(vis[x])continue;vis[x]=true;int disu=now.dis;for(int i=T.head[x];i>0;i=T.e[i].nxt) {int v=T.e[i].to;int w=T.e[i].val;if(vis[v])continue;if(dis[v]>disu+w) {dis[v]=disu+w;q.add(new Node(v, dis[v]));}}}long ans=0;dfs(1,0);f[1][0]=1;for(int i=0;i<=k;++i) {if(fail)break;dfs(n, i);ans=(ans+f[n][i])%md;}if(fail)out.println(-1);else out.println(ans);T=null;Tp=null;inqu=null;dis=null;f=null;O--;}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();}}
}

[SCOI2011]糖果

题目链接

题目大意

$n$ 个人， $k$ 对限制
问在满足限制的条件下，每个人至少有一个糖果时，所需的糖果总数

解题思路

$\left\{\begin{matrix} a=b\Rightarrow a\leq b,b\leq a\Rightarrow a\overset{0}{\rightarrow}b,b\overset{0}{\rightarrow}a\\ a\leq b\Rightarrow a\overset{0}{\rightarrow}b\\ a< b\Rightarrow a+1\leq b\Rightarrow a\overset{1}{\rightarrow}b\\ b\leq a\Rightarrow b\overset{0}{\rightarrow}a\\ b< a\Rightarrow b+1\leq a\Rightarrow b\overset{1}{\rightarrow}a \end{matrix}\right.$
j将限制转化为边建图后，要满足限制，则要跑最长路
将权为 $1$ 的边转为权为 $-1$ ，用 $Spfa$ 跑最短路
若一个点被更新 $n$ 次，则出现负环，无解
初始 $dis_i=-1$ ，表示至少有一个糖果
$ans-=\sum_{i=1}^{n}dis_i$


import java.io.*;
import java.io.ObjectInputStream.GetField;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{
//	static int inf=Integer.MAX_VALUE/2;static boolean fail=false;staticclass Edge{int fr,to,nxt;int val;public Edge(int u,int v,int w) {fr=u;to=v;val=w;}}staticclass Map{Edge[] e;int[] head;int cnt;int vis;public Map(int n,int m) {e=new Edge[m];head=new int[n+1];cnt=0;vis=0;}void addEdge(int fr,int to,int val) {cnt++;e[cnt]=new Edge(fr, to, val);e[cnt].nxt=head[fr];head[fr]=cnt;}long spfa(int n) {boolean[] inqu=new boolean[n+1];int[] dis=new int[n+1];int[] tot=new int[n+1];Queue<Integer> q=new LinkedList<Integer>();for(int i=1;i<=n;++i) {dis[i]=-1;inqu[i]=true;q.add(i);}while(!q.isEmpty()) {int u=q.peek();q.poll();inqu[u]=false;for(int i=head[u];i>0;i=e[i].nxt) {int v=e[i].to;int w=e[i].val;if(dis[v]>dis[u]+w) {dis[v]=dis[u]+w;tot[v]++;if(tot[v]>=n) {fail=true;break;}if(inqu[v])continue;inqu[v]=true;q.add(v);}}if(fail)break;}if(fail)return 0;long ans=0;for(int i=1;i<=n;++i) {ans-=dis[i];}return ans;}}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();Map T=new Map(n, m<<1|1);int[] in=new int[n+1];for(int i=1;i<=m;++i) {int x=input.nextInt();int a=input.nextInt();int b=input.nextInt();//最短路if(x==1) {//a==b=> a<=b,b<=aT.addEdge(a, b, 0);T.addEdge(b, a, 0);}else if(x==2) {//a<b=>a+1<=bif(a==b){out.print("-1");out.flush();out.close();return;}T.addEdge(a, b, -1);}else if(x==3) {//a>=bT.addEdge(b, a, 0);}else if(x==4) {//a>b=>b+1<=aif(a==b){out.print("-1");out.flush();out.close();return;}T.addEdge(b, a, -1);}else {//a<=bT.addEdge(a, b, 0);}}long ans=T.spfa(n);if(fail) {out.print("-1");}else out.print(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();}}
}