@OceanEye7年前
05/29
21:50
T飞了……
前排膜拜PoPoQQQ大神的题解
反正我的SPFA费用流是T飞了……
估计因为不停的memset 一共 \( n^2 \) 次然后就炸了吧
:-(等我学个ZKW的姿势回来再切这道题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
#include <cstdio> #include <algorithm> #include <cstring> #define ll long long #define INF 100000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> inline void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } #define ququq 100000 char bsd[ququq]; int last; inline void output() { puts(bsd); } inline void add(int x,char lc) { static char c[12]; static int node; if(x==0) { bsd[last++]='0';bsd[last++]=lc; return; } node=0; while(x) c[node++]=x%10,x/=10; while(node) bsd[last++]=c[--node]+'0'; bsd[last++]=lc; } using namespace std; #define N 110 #define SIZ 10200 #define S 0 #define T 10199 struct Tedge { int from,to,flow,val; }edge[SIZ<<6]; #define E edge[i] #define TO E.to #define FROM E.from #define FLOW E.flow #define VAL E.val int fst[SIZ],NXT[SIZ<<6],e_tot; void add_e(int from,int to,int cap,int val) { static int &i=e_tot; FROM=from; TO=to; FLOW=cap; VAL=val; NXT[e_tot]=fst[from]; fst[from]=e_tot++; FROM=to; TO=from; FLOW=0; VAL=val; NXT[e_tot]=fst[to]; fst[to]=e_tot++; } int mp[N][N],n,A_[N][N],ans[N][N]; int calc(int i,int j) { if(i>j) swap(i,j); return (i-1)*n+j; } inline void init() { memset(fst,-1,sizeof(fst)); read(n); For(i,1,n) for(int j=1;j<=n;j++) read(mp[i][j]); For(i,1,n) for(int j=0;j<n-1;j++) add_e(S,i,1,j); For(i,1,n) for(int j=1;j<=n;j++) { if(i==j) continue; if(i<j)add_e(calc(i,j)+n,T,1,0); if(mp[i][j]==1||mp[i][j]==2) { add_e(j,calc(i,j)+n,1,0); A_[i][j]=e_tot-1; } } } int p[SIZ],dis[SIZ],ANS; bool inq[SIZ]; void cp(int &x,int y) { x>y?x=y:x=x; } void Augment() { static int node,c,i; node=T; c=INF; while(node!=S) { i=p[node]; cp(c,FLOW); node=FROM; } node=T; while(node!=S) { i=p[node]; FLOW-=c; i^=1; FLOW+=c; node=TO; } ANS-=c*dis[T]; } bool SPFA() { static int x,Q[65540],i; static unsigned short int he=0,ta=0; memset(dis,0x7f,sizeof(dis)); Q[++he]=S; dis[S]=0; inq[S]=true; while(he!=ta) { x=Q[++ta]; inq[x]=false; for(i=fst[x];~i;i=NXT[i]) { if(!FLOW||dis[TO]<=dis[x]+VAL) continue; dis[TO]=dis[x]+VAL; p[TO]=i; if(!inq[TO]) { dis[TO]<dis[Q[ta+1]]?Q[ta--]=TO:Q[++he]=TO; inq[TO]=true; } } } return (dis[T]>INF)?false:true; } int main() { freopen("BZOJ2597.in","r",stdin); init(); ANS=n*(n-1)*(n-2)/6; while(SPFA()) Augment(); add(ANS,'\n'); For(i,1,n) for(int j=1;j<=n;j++) add(!A_[i][j]||!edge[A_[i][j]].flow?0:1,j==n?'\n':' '); output(); return 0; } |