网络流算法
最大流算法和最小费用算法都有贪心的思想，每次迭代都会离最大流网络更近一步。网络流的题目难度主要在抽象建模，很多问题同网络流联系起来并不那边直观。
·
最大流算法：
主要思想就是每次找到一条增广路径，直到网络中不存在增广路径时，就找到了最大流。
最大流算法证明（AI回答）：
最大流最小割定理证明
一、弱对偶性证明
对于任意可行流 ff 和任意割 (S,T)，其流量 ∣f∣ 不超过割的容量c(S,T)，即：
∣f∣≤∑u∈S,v∈Tc(u,v)
论证步骤：
- 流量分解：流的流量 ∣f∣ 可分解为割 (S,T) 中正向边流量之和减反向边流量之和，即：∣f∣=∑u∈S,v∈Tf(u,v)−∑u∈T,v∈Sf(u,v)
- 容量约束：由于 f(u,v)≤c(u,v) 且反向边流量 f(v,u)≥0，可得：∣f∣≤∑u∈S,v∈Tc(u,v)因此，最大流的值必然不超过最小割的容量
最大流算法证明
1. 最大流存在的必要条件
- 任意流的流量不超过任意割的容量：
对于割 (S,T)(，其容量 c(S,T)=∑u∈S,v∈Tc(u,v)，而流 f的流量满足 ∣f∣≤c(S,T)。
2. 算法终止时的流为最大流
- 构造割 (S,T)：当残留网络中无增广路径时，定义集合 S 包含从源点可达的所有节点，T=V∖S。
- 割的流量等于容量：此时 S 到 T 的所有边流量饱和，T 到 S 的边流量为零，因此 ∣f∣=c(S,T)∣。
- 最小割的存在性：由 ∣f∣≤c(S,T) 且构造的割容量等于当前流量，知当前流即为最大流
最小费用最大流算法
主要思想就是每次找到一条费用最小的增广路径，直到找不到网络中的增广路径时，就找到了最大流的最小费用。
最小费用最大流算法证明（AI回答）
1. 初始状态的正确性
- 零流的合法性：初始流 f=0，费用为0，显然满足费用最优性。
2. 归纳假设
假设当前流 f 是所有流量为 ∣f∣ 的可行流中费用最小的。需证明：通过增广一条费用最小的路径 P，得到流 f′，则 f′f′ 是所有流量为 ∣f∣+Δ的流中费用最小的。
3. 关键引理
引理：若每次增广的是残余网络中费用最小的路径，则新流的费用仍为当前流量下的最小值。
证明（反证法）：
- 假设存在更优流：假设存在另一流 f′′，满足 ∣f′′∣=∣f′∣ 且 cost(f′′)<cost(f′)。
- 流分解定理：将流 f′′−f 分解为若干简单路径和环的叠加。由于 cost(f′′−f)<cost(f′−f)，存在至少一条增广路径的费用比当前所选路径 P更低（否则总费用无法更小）。
- 矛盾：这与算法每次选择费用最小的路径增广矛盾，因此假设不成立。
4. 负权边的处理
- 反向边费用补偿：反向边费用为 −a(u,v)，确保增广路径费用计算的正确性。例如，若从 u→v原有流量 f(u,v)，则反向边 v→u允许回退流量，并补偿费用。
- SPFA算法的必要性：由于反向边可能引入负权边，需使用SPFA算法寻找最短路（Dijkstra需结合势函数才可处理负权）。
5. 终止条件
当残余网络中不存在源点到汇点的增广路径时，当前流为最大流。根据归纳法，此时的费用也为最小值
复杂度分析
- 时间复杂度：依赖于增广次数和最短路径算法复杂度。若采用SPFA，复杂度为 O(F⋅VE)（F 为最大流量，E 和 V 为边数和顶点数）。
- 势函数优化：通过势函数将边权调整为非负，可使用Dijkstra算法减少时间复杂度至 O(F⋅(E+VlogV))
总结：
最大流算法和最小费用算法都有贪心的思想，每次迭代都会离最大流网络更近一步。网络流的问题难度主要在抽象建模，很多问题同网络流联系起来并不那边直观。那些可以分成2组节点相互连边的问题通常可以转换为网络流解决，比如二分图匹配。因为引入了反向边，每次找增广路时需要更新正向边和反向边的流量，就需要快查找到增广路径上的边。所以在网络流算法中一般用链式前向星（邻接矩阵不支持两点间连多条边，邻接表不支持快速定位到对应的边）这种数据结构表示图比较高效方便。需要注意反向边的容量为0，花费为负。
最大流算法代码实现
题目：E. Soldier and Traveling
https://codeforces.com/problemset/problem/546/E
思路：n个值建对应n个节点，分配给n个位置对应n个节点 。原点到n个节点连边的流量为初始值，n个位置到终点的流量为期望值。需要检测最终的残余网络，输出边的分配情况
Edmonds-Karp算法
复杂度O(V*E^2)，证明
https://www.zhihu.com/question/65133832/answer/2306908696
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String args[]) {new Main().run();}
FastReader in = new FastReader();
PrintWriter out = new PrintWriter(System.out);
void run() {
work();
out.flush();
}
long mod=998244353;
long inf=Long.MAX_VALUE/3;
long gcd(long a,long b) {
return a==0?b:gcd(b%a,a);
}
Edge[] edges;
int[] head;
int[] route;
int maxn=220;
int S,T;
int cur;
void addEdge(int s,int e,int flow,int cap){
Edge edge=new Edge(s,e,flow,cap,head[s]);
edges[cur]=edge;
head[s]=cur;
cur++;
}
void work(){
head=new int[maxn];
Arrays.fill(head, -1);
route=new int[maxn];
edges=new Edge[maxn*200];
int n=ni(),m=ni();
int[] A=nia(n);
int[] B=nia(n);
int sum=0,sum1=0;
for(int i=0;i<n;i++){
sum+=A[i];
sum1+=B[i];
}
S=0;T=maxn-1;
//S(0),n个值(1——n)，n个位置（n+1——2*n），T
//S连n个值
for(int i=0;i<n;i++){
addEdge(S,1+i,0,A[i]);
addEdge(1+i,S,0,0);
}
//n个位置连T
for(int i=0;i<n;i++){
addEdge((n+1+i),T,0,B[i]);
addEdge(T,(n+1+i),0,0);
}
//n个值连n个位置
for(int i=0;i<n;i++){
addEdge(1+i,(n+1+i),0,A[i]);
addEdge((n+1+i),1+i,0,0);
}
//m条边
for(int i=0;i<m;i++){
int s=ni()-1,e=ni()-1;
addEdge(s+1,(n+1+e),0,A[s]);
addEdge((n+1+e),s+1,0,0);
addEdge(e+1,(n+1+s),0,A[e]);
addEdge((n+1+s),e+1,0,0);
}
int ret=ek();
if(ret!=sum||sum1!=sum){
out.println("NO");
return;
}
out.println("YES");
int[][] rec=new int[n][n];
for(int i=0;i<edges.length&&edges[i]!=null;i++){
Edge edge = edges[i];
if(edge.from<edge.to&&edge.from!=S&&edge.to!=T){
//找出值到位置的边
rec[edge.from-1][edge.to-n-1]=edge.flow;
}
}
for(int[] R:rec){
for(int r:R){
out.print(r+" ");
}
out.println();
}
}
//最大流Edmonds-Karp
int ek(){
int ret=0;
while(true){
LinkedList<Integer> queue=new LinkedList<>();
queue.add(S);
boolean[] vis=new boolean[maxn];
int[] rec=new int[maxn];//当前增广路增加的流量
Arrays.fill(rec,999999999);
Arrays.fill(route,-1);
vis[S]=true;
while(queue.size()>0){
Integer node = queue.poll();
for(int i=head[node];i!=-1;i=edges[i].next){
Edge edge = edges[i];
if(!vis[edge.to]&&edge.flow<edge.cap){
rec[edge.to]=Math.min(rec[node],edge.cap-edge.flow);
route[edge.to]=i;
queue.add(edge.to);
vis[edge.to]=true;
}
}
}
if(rec[T]==999999999) break;
ret+=rec[T];
//更新流量
for(int i=route[T];i!=-1;i=route[edges[i].from]){
// c+=edges[i].cost;
edges[i].flow+=rec[T];
edges[i^1].flow-=rec[T];//注意：i是奇数或偶数时不同
}
}
return ret;
}
class Edge{
int from,to,flow,cap,next;
Edge(int from,int to,int flow,int cap,int next){
this.from=from;
this.to=to;
this.flow=flow;
this.cap=cap;
this.next=next;
}
}
@SuppressWarnings("unused")
private ArrayList<Integer>[] ng(int n, int m) {
ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];
for(int i=0;i<n;i++) {
graph[i]=new ArrayList<>();
}
for(int i=1;i<=m;i++) {
int s=in.nextInt()-1,e=in.nextInt()-1;
graph[s].add(e);
graph[e].add(s);
}
return graph;
}
private ArrayList<long[]>[] ngw(int n, int m) {
ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
for(int i=0;i<n;i++) {
graph[i]=new ArrayList<>();
}
for(int i=1;i<=m;i++) {
long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
graph[(int)s].add(new long[] {e,w});
graph[(int)e].add(new long[] {s,w});
}
return graph;
}
private int ni() {
return in.nextInt();
}
private long nl() {
return in.nextLong();
}
private double nd() {
return in.nextDouble();
}
private String ns() {
return in.next();
}
private long[] na(int n) {
long[] A=new long[n];
for(int i=0;i<n;i++) {
A[i]=in.nextLong();
}
return A;
}
private int[] nia(int n) {
int[] A=new int[n];
for(int i=0;i<n;i++) {
A[i]=in.nextInt();
}
return A;
}
}
class FastReader
{
BufferedReader br;
StringTokenizer st;
InputStreamReader input;//no buffer
public FastReader()
{
br=new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(boolean isBuffer)
{
if(!isBuffer){
input=new InputStreamReader(System.in);
}else{
br=new BufferedReader(new InputStreamReader(System.in));
}
}
public boolean hasNext(){
try{
String s=br.readLine();
if(s==null){
return false;
}
st=new StringTokenizer(s);
}catch(IOException e){
e.printStackTrace();
}
return true;
}
public String next()
{
if(input!=null){
try {
StringBuilder sb=new StringBuilder();
int ch=input.read();
while(ch=='\n'||ch=='\r'||ch==32){
ch=input.read();
}
while(ch!='\n'&&ch!='\r'&&ch!=32){
sb.append((char)ch);
ch=input.read();
}
return sb.toString();
}catch (Exception e){
e.printStackTrace();
}
}
while(st==null || !st.hasMoreElements())//回车，空行情况
{
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return (int)nextLong();
}
public long nextLong() {
try {
if(input!=null){
long ret=0;
int b=input.read();
while(b<'0'||b>'9'){
b=input.read();
}
while(b>='0'&&b<='9'){
ret=ret*10+(b-'0');
b=input.read();
}
return ret;
}
}catch (Exception e){
e.printStackTrace();
}
return Long.parseLong(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
}dinic算法
找增广路径时每次不需要从头开始搜索，复杂度O(V^2*E)，证明讨论 - 力扣（LeetCode）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String args[]) {new Main().run();}
FastReader in = new FastReader();
PrintWriter out = new PrintWriter(System.out);
void run() {
work();
out.flush();
}
long mod=998244353;
int inf=999999999;
long gcd(long a,long b) {
return a==0?b:gcd(b%a,a);
}
Edge[] edges;
int[] head;
int[] route;
int[] deep;
int maxn=220;
int S,T;
int cur;
void addEdge(int s,int e,int flow,int cap){
Edge edge=new Edge(s,e,flow,cap,head[s]);
edges[cur]=edge;
head[s]=cur;
cur++;
}
void work(){
head=new int[maxn];
deep=new int[maxn];
Arrays.fill(head, -1);
route=new int[maxn];
edges=new Edge[maxn*200];
int n=ni(),m=ni();
int[] A=nia(n);
int[] B=nia(n);
int sum=0,sum1=0;
for(int i=0;i<n;i++){
sum+=A[i];
sum1+=B[i];
}
S=0;T=maxn-1;
//S(0),n个值(1——n)，n个位置（n+1——2*n），T
//S连n个值
for(int i=0;i<n;i++){
addEdge(S,1+i,0,A[i]);
addEdge(1+i,S,0,0);
}
//n个位置连T
for(int i=0;i<n;i++){
addEdge((n+1+i),T,0,B[i]);
addEdge(T,(n+1+i),0,0);
}
//n个值连n个位置
for(int i=0;i<n;i++){
addEdge(1+i,(n+1+i),0,A[i]);
addEdge((n+1+i),1+i,0,0);
}
//m条边
for(int i=0;i<m;i++){
int s=ni()-1,e=ni()-1;
addEdge(s+1,(n+1+e),0,A[s]);
addEdge((n+1+e),s+1,0,0);
addEdge(e+1,(n+1+s),0,A[e]);
addEdge((n+1+s),e+1,0,0);
}
int ret=dinic();
if(ret!=sum||sum1!=sum){
out.println("NO");
return;
}
out.println("YES");
int[][] rec=new int[n][n];
for(int i=0;i<edges.length&&edges[i]!=null;i++){
Edge edge = edges[i];
if(edge.from<edge.to&&edge.from!=S&&edge.to!=T){
//找出值到位置的边
rec[edge.from-1][edge.to-n-1]=edge.flow;
}
}
for(int[] R:rec){
for(int r:R){
out.print(r+" ");
}
out.println();
}
}
//最大流dinic，不需要记录路径，因为在dfs中已经更新了
int dinic(){
int ret=0;
while(bfs()){
ret+=dfs(S,inf);
}
return ret;
}
private boolean bfs() {
LinkedList<Integer> queue=new LinkedList<>();
queue.add(S);
Arrays.fill(deep,-1);
deep[S]=0;
while(queue.size()>0){
Integer node = queue.poll();
for(int i=head[node];i!=-1;i=edges[i].next){
Edge edge = edges[i];
if(deep[edge.to]==-1&&edge.flow<edge.cap){
deep[edge.to]=deep[node]+1;
queue.add(edge.to);
}
}
}
if(deep[T]==-1)return false;
return true;
}
private int dfs(int node,int limit) {//limit为前面连接的最小流量
if(node==T||limit==0) return limit;
int flow=0;
for(int i=head[node];i!=-1;i=edges[i].next){
Edge edge = edges[i];
if(deep[edge.to]==deep[node]+1&&edge.flow<edge.cap){
int r=dfs(edge.to,Math.min(limit,edge.cap-edge.flow));//r为后面路径的流量
limit-=r;
flow+=r;
edges[i].flow+=r;
edges[i^1].flow-=r;
if(limit==0)break;
}
}
return flow;
}
class Edge{
int from,to,flow,cap,next;
Edge(int from,int to,int flow,int cap,int next){
this.from=from;
this.to=to;
this.flow=flow;
this.cap=cap;
this.next=next;
}
}
@SuppressWarnings("unused")
private ArrayList<Integer>[] ng(int n, int m) {
ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];
for(int i=0;i<n;i++) {
graph[i]=new ArrayList<>();
}
for(int i=1;i<=m;i++) {
int s=in.nextInt()-1,e=in.nextInt()-1;
graph[s].add(e);
graph[e].add(s);
}
return graph;
}
private ArrayList<long[]>[] ngw(int n, int m) {
ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
for(int i=0;i<n;i++) {
graph[i]=new ArrayList<>();
}
for(int i=1;i<=m;i++) {
long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
graph[(int)s].add(new long[] {e,w});
graph[(int)e].add(new long[] {s,w});
}
return graph;
}
private int ni() {
return in.nextInt();
}
private long nl() {
return in.nextLong();
}
private double nd() {
return in.nextDouble();
}
private String ns() {
return in.next();
}
private long[] na(int n) {
long[] A=new long[n];
for(int i=0;i<n;i++) {
A[i]=in.nextLong();
}
return A;
}
private int[] nia(int n) {
int[] A=new int[n];
for(int i=0;i<n;i++) {
A[i]=in.nextInt();
}
return A;
}
}
class FastReader
{
BufferedReader br;
StringTokenizer st;
InputStreamReader input;//no buffer
public FastReader()
{
br=new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(boolean isBuffer)
{
if(!isBuffer){
input=new InputStreamReader(System.in);
}else{
br=new BufferedReader(new InputStreamReader(System.in));
}
}
public boolean hasNext(){
try{
String s=br.readLine();
if(s==null){
return false;
}
st=new StringTokenizer(s);
}catch(IOException e){
e.printStackTrace();
}
return true;
}
public String next()
{
if(input!=null){
try {
StringBuilder sb=new StringBuilder();
int ch=input.read();
while(ch=='\n'||ch=='\r'||ch==32){
ch=input.read();
}
while(ch!='\n'&&ch!='\r'&&ch!=32){
sb.append((char)ch);
ch=input.read();
}
return sb.toString();
}catch (Exception e){
e.printStackTrace();
}
}
while(st==null || !st.hasMoreElements())//回车，空行情况
{
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return (int)nextLong();
}
public long nextLong() {
try {
if(input!=null){
long ret=0;
int b=input.read();
while(b<'0'||b>'9'){
b=input.read();
}
while(b>='0'&&b<='9'){
ret=ret*10+(b-'0');
b=input.read();
}
return ret;
}
}catch (Exception e){
e.printStackTrace();
}
return Long.parseLong(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
}最小费用最大流算法代码实现：
https://codeforces.com/contest/863/problem/F
该题的关键在于构造图，构造1个节点（下标0）代表原点S，n个节点（下标1到n）代表从1到n的n个值，n个节点（下标n+1到2n）代表从1到n的n个位置，1个终点T。其中原点到每个下标1到n的点都连50条边，费用为2*j-1，（j表示第j条边），下标1到n的点根据题目条件限制分别连上多条边到下标n+1到2*n的点，每个下标n+1到2*n的点在连一条边到终点，其中流量都为1。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String args[]) {new Main().run();}
FastReader in = new FastReader();
PrintWriter out = new PrintWriter(System.out);
void run() {
work();
out.flush();
}
long mod=998244353;
long inf=Long.MAX_VALUE/3;
long gcd(long a,long b) {
return a==0?b:gcd(b%a,a);
}
Edge[] edges;
int[] head;
int[] route;
int maxn=120;
int S,T;
int cur;
void addEdge(int s,int e,int flow,int cap,int cost){
Edge edge=new Edge(s,e,flow,cap,cost,head[s]);
edges[cur]=edge;
head[s]=cur;
cur++;
}
void work(){
int n=ni();
edges=new Edge[maxn*100];
head=new int[maxn];
Arrays.fill(head,-1);
route=new int[maxn];
boolean[][] rec=new boolean[n+1][n+1];
for(int q=ni();q>0;q--){
int t=ni(),l=ni(),r=ni(),v=ni();
if(t==1){
for(int i=l;i<=r;i++){
for(int j=1;j<v;j++)rec[i][j]=true;
}
}else{
for(int i=l;i<=r;i++){
for(int j=v+1;j<=n;j++)rec[i][j]=true;
}
}
}
//S=0,T=110
S=0;T=110;
//添加值1——n
for(int i=1;i<=n;i++){
for(int j=0;j<n;j++){
addEdge(S,i,0,1,2*j+1);
addEdge(i,S,0,0,-(2*j+1));
}
}
//位置n+1——2*n
for(int i=1;i<=n;i++){
boolean f=false;
for(int j=1;j<=n;j++){
if(!rec[i][j]){
f=true;
addEdge(j,i+n,0,1,0);
addEdge(i+n,j,0,0,0);
}
}
if(!f){
out.println(-1);
return;
}
}
for(int i=1;i<=n;i++){
addEdge(i+n,T,0,1,0);
addEdge(T,i+n,0,0,0);
}
out.println(mcmf());
}
//最小费用最大流Minimum Cost Maximum Flow
int mcmf(){
int sumCost=0;
int maxFlow=0;
while(spfa()){
int v=999999999;
//查找最小流量
for(int i=route[T];i!=-1;i=route[edges[i].from]){
v=Math.min(v,edges[i].cap-edges[i].flow);
}
//更新流量
for(int i=route[T];i!=-1;i=route[edges[i].from]){
// c+=edges[i].cost;
edges[i].flow+=v;
edges[i^1].flow-=v;//注意：i是奇数或偶数时不同
}
}
for(int i=0;i<edges.length&&edges[i]!=null;i+=2){
Edge edge=edges[i];
sumCost+=edge.flow*edge.cost;
//最大流==某一个割中的S部分的点流向T部分点的流-T部分的点流向S部分点的流
//这里已T点的边为割，T部分的点流向S部分点的流为0
if(edge.to==T){
maxFlow+=edge.flow;
}
}
return sumCost;
}
//用于求含负权边的单源最短路径
boolean spfa(){
LinkedList<Integer> queue=new LinkedList<>();
queue.add(S);
boolean[] vis=new boolean[maxn];
int[] rec=new int[maxn];
Arrays.fill(rec,999999999);
Arrays.fill(route,-1);
rec[S]=0;
while(queue.size()>0){
Integer node = queue.poll();
vis[node]=false;
for(int i=head[node];i!=-1;i=edges[i].next){
Edge edge = edges[i];
if(rec[edge.to]>rec[node]+edge.cost&&edge.flow<edge.cap){
rec[edge.to]=rec[node]+edge.cost;
route[edge.to]=i;
if(!vis[edge.to]){
queue.add(edge.to);
vis[edge.to]=true;
}
}
}
}
if(rec[T]==999999999){
return false;
}
return true;
}
class Edge{
int from,to,flow,cap,cost,next;
Edge(int from,int to,int flow,int cap,int cost,int next){
this.from=from;
this.to=to;
this.flow=flow;
this.cap=cap;
this.cost=cost;
this.next=next;
}
}
@SuppressWarnings("unused")
private ArrayList<Integer>[] ng(int n, int m) {
ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];
for(int i=0;i<n;i++) {
graph[i]=new ArrayList<>();
}
for(int i=1;i<=m;i++) {
int s=in.nextInt()-1,e=in.nextInt()-1;
graph[s].add(e);
graph[e].add(s);
}
return graph;
}
private ArrayList<long[]>[] ngw(int n, int m) {
ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
for(int i=0;i<n;i++) {
graph[i]=new ArrayList<>();
}
for(int i=1;i<=m;i++) {
long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
graph[(int)s].add(new long[] {e,w});
graph[(int)e].add(new long[] {s,w});
}
return graph;
}
private int ni() {
return in.nextInt();
}
private long nl() {
return in.nextLong();
}
private double nd() {
return in.nextDouble();
}
private String ns() {
return in.next();
}
private long[] na(int n) {
long[] A=new long[n];
for(int i=0;i<n;i++) {
A[i]=in.nextLong();
}
return A;
}
private int[] nia(int n) {
int[] A=new int[n];
for(int i=0;i<n;i++) {
A[i]=in.nextInt();
}
return A;
}
}
class FastReader
{
BufferedReader br;
StringTokenizer st;
InputStreamReader input;//no buffer
public FastReader()
{
br=new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(boolean isBuffer)
{
if(!isBuffer){
input=new InputStreamReader(System.in);
}else{
br=new BufferedReader(new InputStreamReader(System.in));
}
}
public boolean hasNext(){
try{
String s=br.readLine();
if(s==null){
return false;
}
st=new StringTokenizer(s);
}catch(IOException e){
e.printStackTrace();
}
return true;
}
public String next()
{
if(input!=null){
try {
StringBuilder sb=new StringBuilder();
int ch=input.read();
while(ch=='\n'||ch=='\r'||ch==32){
ch=input.read();
}
while(ch!='\n'&&ch!='\r'&&ch!=32){
sb.append((char)ch);
ch=input.read();
}
return sb.toString();
}catch (Exception e){
e.printStackTrace();
}
}
while(st==null || !st.hasMoreElements())//回车，空行情况
{
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return (int)nextLong();
}
public long nextLong() {
try {
if(input!=null){
long ret=0;
int b=input.read();
while(b<'0'||b>'9'){
b=input.read();
}
while(b>='0'&&b<='9'){
ret=ret*10+(b-'0');
b=input.read();
}
return ret;
}
}catch (Exception e){
e.printStackTrace();
}
return Long.parseLong(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
7
0- 0
已为社区贡献5条内容
所有评论(0)