AtCoder Beginner Contest 247 G - Dream Team 解題心得( 題目 )
解題概念:Min cost flow
解題方法:本來是max flow，加個負號，變成min cost，可使用SPFA找最短路徑(這題無負環不會worst case)，所以時間複雜度是好的。
//Author:En Chi Tsung(欉恩祁)
//Date:2022/06/22
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static long ret,bt;
public static int reti,rd,last;
public static boolean neg;
public static final int mod=998244353;
public static final int mod2=1_000_000_007;
public static final int maxn=155,max=maxn+5, max2=max*4+5,maxp=35005;
public static final int sink=maxn*2+1;
public static Useful us=new Useful(mod2);
public static long[] d=new long[max2];
public static int[] f=new int[maxp];
public static int[] c=new int[maxp];
public static Pii[] pre=new Pii[max2];
public static int[] in=new int[max2];
public static ArrayList<ArrayList<Pii>> e=new ArrayList<>();
public static long ans=0;
public static void main(String[] args) throws Exception{
for(int i=0;i<=max2;i++) {
e.add(new ArrayList<>());
}
final int n=readint();
int cnt=n+1,x,y;
for(int i=1;i<=n;i++) {
x=readint();
y=readint()+maxn;
f[i]=1;
c[i]=-readint();
e.get(x).add(new Pii(1,i,y));
e.get(y).add(new Pii(-1,i,x));
}
for(int i=1;i<=maxn;i++,cnt++) {
f[cnt]=1;
c[cnt]=0;
e.get(0).add(new Pii(1,cnt,i));
e.get(i).add(new Pii(-1,cnt,0));
}
for(int i=1;i<=maxn;i++,cnt++) {
f[cnt]=1;
c[cnt]=0;
e.get(sink).add(new Pii(-1,cnt,i+maxn));
e.get(i+maxn).add(new Pii(1,cnt,sink));
}
ArrayList<Long> an=new ArrayList<>();
while(spfa()) {
an.add(-ans);
}
bw.write(an.size()+"\n");
for(Long i:an) {
bw.write(i+"\n");
}
bw.flush();
}
public static boolean spfa() {
bt=(1L<<59);
us.arr(in,0);
us.arr(d,(1L<<59));
d[0]=0;
Queue<Integer> q=new LinkedList<>();
q.offer(0);
pre[sink]=null;
int o;
int top=-1;
while(!q.isEmpty()) {
o=q.poll();
for(Pii i:e.get(o)) {
if(d[o]+i.rev*c[i.x]<d[i.y]&&i.rev*f[i.x]>0) {
d[i.y]=d[o]+i.rev*c[i.x];
pre[i.y]=new Pii(i.rev,i.x,o);
if(in[i.y]==0) {
q.offer(i.y);
in[i.y]=1;
}
}
}
in[o]=0;
}
top=sink;
if(pre[top]==null) {
return false;
}
ans+=d[sink];
while(true) {
f[pre[top].x]-=2*(pre[top].rev);
if(pre[top].y==0) {
break;
}
top=pre[top].y;
}
return true;
}
public static int readint() throws Exception{
reti=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
reti*=10;
reti+=(rd&15);
rd=br.read();
}
if(neg)reti*=-1;
return reti;
}
public static long readlong() throws Exception{
ret=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
/*
*/
/*
*/
class Pii{
int rev,x,y;
Pii(int r,int a,int b){
rev=r;
x=a;
y=b;
}
}
class Pll{
long x,y;
Pll(long a,long b){
x=a;
y=b;
}
}
class Useful{
long mod;
Useful(long m){mod=m;}
void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}}
void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
long fast(long x,long pw) {
if(pw<=0)return 1;
if(pw==1)return x;
long h=fast(x,pw>>1);
if((pw&1)==0) {
return h*h%mod;
}
return h*h%mod*x%mod;
}
long[][] mul(long[][] a,long[][] b){
long[][] c=new long[a.length][b[0].length];
for(int i=0;i<a.length;i++) {
for(int j=0;j<b[0].length;j++) {
for(int k=0;k<a[0].length;k++) {
c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
}
}
return c;
}
long[][] fast(long[][] x,int pw){
if(pw==1)return x;
long[][] h=fast(x,pw>>1);
if((pw&1)==0) {
return mul(h,h);
}
else {
return mul(mul(h,h),x);
}
}
int gcd(int a,int b) {
if(a==0)return b;
if(b==0)return a;
return gcd(b,a%b);
}
long gcd(long a,long b) {
if(a==0)return b;
if(b==0)return a;
return gcd(b,a%b);
}
long lcm(long a, long b){
return a*(b/gcd(a,b));
}
double log2(int x) {
return (Math.log(x)/Math.log(2));
}
double log2(long x) {
return (Math.log(x)/Math.log(2));
}
}
文章標籤
全站熱搜
