BZOJ
洛谷

---

\(Description\)
給定一張部分邊方向已確定的競賽圖。你需要給剩下的邊確定方向，使得圖中的三元環數量最多。
\(n\leq100\)。

---

\(Solution\)
這種選擇之間有影響，而且\(n\)很小的題考慮網絡流啊。

最理想的情況能得到的三元環個數是\(C_n^3\)個。我們考慮怎樣會使三元環個數減少。
如果三個點之間不成三元環，那么一定是某個點入度為\(2\)，某個點出度為\(2\)，另一個點入度出度都為\(1\)。
不妨只考慮入度。如果一個點入度為\(2\)，那么會減少\(1\)個三元環；如果入度為\(3\)，那么會減少\(C_3^2=3\)個三元環（設連向該點\(A\)的三個點為\(B,C,D\)，\(A,B,C\)、\(A,B,D\)、\(A,C,D\)之間都形不成三元環）...
也就是設一個點的入度為\(dgr\)，會減少\(C_{dgr}^2\)個三元環。那么答案就是\(C_n^3-\sum_{i=1}^nC_{dgr_i}^2\)。
而度數每次改變\(1\)，減少的三元環個數是\(C_{dgr}^2-C_{dgr-1}^2=dgr-1\)。

然后就可以考慮給每個點分配度數了。對每條邊新建一個點\(x\)，由源點向\(x\)連容量\(1\)、費用\(0\)的邊，\(x\)向邊的兩端點分別連容量為\(1\)、費用為\(0\)的邊。
對于原圖的\(n\)個點，每個點向匯點分別連容量為\(1\)，費用為\(0,1,2,3...\)的邊。
跑費用流，\(C_n^3-cost\)就是答案了。

實現上，對于確定的邊并不需要建出來，把答案先減掉\(\frac{dgr_i(dgr_i-1)}{2}\)；然后枚舉\(i\)連向匯點的邊時，費用從\(dgr_i\)開始枚舉就可以了。（優化很明顯）

數組memset(A,...,某個確定大小)，注意A[]是int還是bool！bool是一字節！

另外有種隨機化+迭代的做法，跑得很快：

---

SPFA：（日常被zkw吊打）

//3032kb 3700ms #include <queue> #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> //#define gc() getchar() #define MAXIN 300000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=105+105*52,M=4*105*105*2;int src,des,Enum,H[N],nxt[M],fr[M],to[M],cap[M],cost[M],pre[N]; char IN[MAXIN],*SS=IN,*TT=IN;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-48,c=gc());return now; } inline void AE(int u,int v,int w,int c) {to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w, cost[Enum]=c;to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=0, cost[Enum]=-c; } bool SPFA() {static int dis[N];static bool inq[N];static std::queue<int> q;memset(dis,0x3f,des+1<<2);dis[0]=0, q.push(0);while(!q.empty()){int x=q.front(); q.pop();inq[x]=0;for(int i=H[x],v; i; i=nxt[i])if(cap[i] && dis[v=to[i]]>dis[x]+cost[i])dis[v]=dis[x]+cost[i], pre[v]=i, !inq[v]&&(q.push(v),inq[v]=1);}return dis[des]<0x3f3f3f3f; } inline int Augment() {int res=0;for(int i=des; i; i=fr[pre[i]])res+=cost[pre[i]], --cap[pre[i]], ++cap[pre[i]^1];return res; } int MCMF() {int res=0;while(SPFA()) res+=Augment();return res; }int main() {static int dgr[105],id[N],tag[N],Ans[105][105];const int n=read(); Enum=1, src=0, des=(n*n+n)/2+1;if(n<3) return putchar('0'),0;for(int i=1,tot=n; i<=n; ++i){for(int j=1; j<=i; ++j) read();for(int j=i+1; j<=n; ++j)switch(AE(0,++tot,1,0),read()){case 0: tag[tot]=1, ++dgr[j]; break;case 1: tag[tot]=2, ++dgr[i]; break;case 2: AE(tot,i,1,0), id[tot]=Enum, AE(tot,j,1,0); break;//->i: i wins}}int ans=n*(n-1)*(n-2)/6;for(int i=1; i<=n; ++i){ans-=dgr[i]*(dgr[i]-1)/2;for(int j=dgr[i]; j<n-1; ++j) AE(i,des,1,j);}printf("%d\n",ans-MCMF());for(int i=1,tot=n; i<=n; ++i)for(int j=i+1; j<=n; ++j)if(tag[++tot]) Ans[i][j]=tag[tot]-1;else Ans[i][j]=cap[id[tot]]?1:0;for(int i=1; i<=n; ++i,putchar('\n')){for(int j=1; j<i; ++j) printf("%d ",Ans[j][i]^1);for(int j=i; j<=n; ++j) printf("%d ",Ans[i][j]);}return 0; }

---

zkw：

//2292kb 416ms #include <queue> #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> //#define gc() getchar() #define MAXIN 300000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) typedef long long LL; const int N=105+105*52,M=4*105*105*2;int src,des,Cost,Enum,cur[N],H[N],nxt[M],fr[M],to[M],cap[M],cost[M],dis[N]; bool vis[N]; char IN[MAXIN],*SS=IN,*TT=IN;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-48,c=gc());return now; } inline void AE(int u,int v,int w,int c) {to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w, cost[Enum]=c;to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=0, cost[Enum]=-c; } bool SPFA() {static bool inq[N];static std::queue<int> q;memset(dis,0x3f,des+1<<2);dis[0]=0, q.push(0);while(!q.empty()){int x=q.front(); q.pop();inq[x]=0;for(int i=H[x],v; i; i=nxt[i])if(cap[i] && dis[v=to[i]]>dis[x]+cost[i])dis[v]=dis[x]+cost[i], !inq[v]&&(q.push(v),inq[v]=1);}return dis[des]<0x3f3f3f3f; } int DFS(int x) {if(x==des) return 1;vis[x]=1;for(int &i=cur[x]; i; i=nxt[i])if(!vis[to[i]] && cap[i] && dis[to[i]]==dis[x]+cost[i] && DFS(to[i]))return --cap[i],++cap[i^1],Cost+=cost[i],1;return 0; } int MCMF() {while(SPFA()){memcpy(cur,H,des+1<<2), memset(vis,0,des+1);//bool是1字節！！！while(DFS(0));}return Cost; }int main() {static int dgr[105],id[N],tag[N],Ans[105][105];const int n=read(); Enum=1, src=0, des=(n*n+n)/2+1;if(n<3) return putchar('0'),0;for(int i=1,tot=n; i<=n; ++i){for(int j=1; j<=i; ++j) read();for(int j=i+1; j<=n; ++j)switch(AE(0,++tot,1,0),read()){case 0: tag[tot]=1, ++dgr[j]; break;case 1: tag[tot]=2, ++dgr[i]; break;case 2: AE(tot,i,1,0), id[tot]=Enum, AE(tot,j,1,0); break;//->i: i wins}}int ans=n*(n-1)*(n-2)/6;for(int i=1; i<=n; ++i){ans-=dgr[i]*(dgr[i]-1)/2;for(int j=dgr[i]; j<n-1; ++j) AE(i,des,1,j);}printf("%d\n",ans-MCMF());for(int i=1,tot=n; i<=n; ++i)for(int j=i+1; j<=n; ++j)if(tag[++tot]) Ans[i][j]=tag[tot]-1;else Ans[i][j]=cap[id[tot]]?1:0;for(int i=1; i<=n; ++i,putchar('\n')){for(int j=1; j<i; ++j) printf("%d ",Ans[j][i]^1);for(int j=i; j<=n; ++j) printf("%d ",Ans[i][j]);}return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/10299901.html

總結

以上是生活随笔為你收集整理的BZOJ.2597.[WC2007]剪刀石头布(费用流zkw)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。