最近開始做荒廢了好久的USACO,希望能夠以一天一個Section的速度做完吧。題解也會每天更新。

Drainage Ditches（ditch）

本題是個最基本的網(wǎng)絡流。這里我用的Dinic算法，遞歸和非遞歸的版本如下：

/* ID:### PROG:ditch LANG:C++ */ #include <memory.h> #include <iostream> #include <stdio.h> using namespace std; const int MAXN = 250,MAXM = 500, inf = 0x7fffffff; struct edge{edge *next,*op;int w,t; }*V[MAXN],ES[MAXM];int lv[MAXN],d[MAXN]; int N,M,EC = 0; int maxflow = 0; void addedge(int a,int b,int w); void init(); void dinic(); bool Dinic_Lable(); inline int min(int a,int b) {if (a>b)return b;else return a; } int Dinic_Argument(int s ,int low = inf); int main() {init();dinic();return 0; } void addedge(int a,int b,int w) {int i,j,k;edge *e;for (e = V[a]; e; e = e->next) if (e->t == b) break;if (e) {e->w += w;return;}ES[++EC].next = V[a]; V[a] = EC+ES; ES[EC].t = b; ES[EC].w = w; ES[EC].op = ES + EC + 1;ES[++EC].next = V[b]; V[b] = ES+EC; ES[EC].t = a; ES[EC].w = 0; ES[EC].op = ES + EC - 1; } void init() {freopen("ditch.in","r",stdin);freopen("ditch.out","w",stdout);int w,i,j,k,a,b;cin>>M>>N;for ( i = 1; i <= M; i++){cin>>a>>b>>w;addedge(a,b,w);}} void dinic() {while (Dinic_Lable()) maxflow += Dinic_Argument(1);printf("%d\n",maxflow);} bool Dinic_Lable() {int i,j,k,head,tail;memset(lv,-1,sizeof(lv));lv[1] = 0;d[0] = 1; head = tail = 0;while (head <= tail){j = d[head++];for (edge *e = V[j]; e; e = e->next){if ( lv[e->t] == -1 && e->w >0){lv[e->t] = lv[j] + 1;d[++tail] = e->t;}}}if (lv[N] == -1 ) return false; else return true; } int Dinic_Argument(int s,int low) {if ( s == N) return low;int i,j,k;j = low;for (edge *e = V[s]; e; e = e->next){if ( lv[e->t] == lv[s] + 1 && j && e->w >0){k = Dinic_Argument(e->t,min(j,e->w));j -= k;e->w -= k;e->op->w += k;}}return low - j; } Dinic 遞歸 /* ID:### PROG:ditch LANG:C++ */ #include <memory.h> #include <iostream> #include <stdio.h> using namespace std; const int MAXN = 250,MAXM = 500, inf = 0x7fffffff; struct edge{edge *next,*op;int w,t; }*V[MAXN],ES[MAXM],*P[MAXN],*stae[MAXM];int lv[MAXN],d[MAXN]; int N,M,EC = 0; int maxflow = 0; void addedge(int a,int b,int w); void init(); void dinic(); bool Dinic_Lable(); inline int min(int a,int b) {if (a>b)return b;else return a; } int Dinic_Argument(int s ,int low = inf); int main() {init();dinic();return 0; } void addedge(int a,int b,int w) {int i,j,k;edge *e;for (e = V[a]; e; e = e->next) if (e->t == b) break;if (e) {e->w += w;return;}ES[++EC].next = V[a]; V[a] = EC+ES; ES[EC].t = b; ES[EC].w = w; ES[EC].op = ES + EC + 1;ES[++EC].next = V[b]; V[b] = ES+EC; ES[EC].t = a; ES[EC].w = 0; ES[EC].op = ES + EC - 1; } void init() {freopen("ditch.in","r",stdin);freopen("ditch.out","w",stdout);int w,i,j,k,a,b;cin>>M>>N;for ( i = 1; i <= M; i++){cin>>a>>b>>w;addedge(a,b,w);}} void dinic() {while (Dinic_Lable()) maxflow += Dinic_Argument(1);printf("%d\n",maxflow);} bool Dinic_Lable() {int i,j,k,head,tail;memset(lv,-1,sizeof(lv));lv[1] = 0;d[0] = 1; head = tail = 0;while (head <= tail){j = d[head++];for (edge *e = V[j]; e; e = e->next){if ( lv[e->t] == -1 && e->w >0){lv[e->t] = lv[j] + 1;d[++tail] = e->t;}}}if (lv[N] == -1 ) return false; else return true; } int Dinic_Argument(int s,int low) {int i,j,k; int stop,t = N, flow = 0;for (i = 0 ; i < MAXN; i++) P[i] = V[i];d[stop = 1] = 1;while (stop){j = d[stop];if ( j != t){for (; P[j]; P[j] = P[j]->next){if (P[j] -> w >0 && lv[P[j]->t] == lv[j] + 1) break;}if (!P[j]) {stop --; lv[j] = -1;}else {d[++stop] = P[j]->t;stae[stop] = P[j];}}else {k = inf;for (i = stop; i > 1; i--){if( k>stae[i]->w) k = stae[i]->w;}for (i = stop; i > 1; i--){stae[i]->w -= k;stae[i]->op->w += k;}flow += k;for (i = 2; i <= stop; i++) if (stae[i]->w == 0 ) break;stop = i - 2;}}return flow; } Dinic 非遞歸

The perfect stall(stall4)

依然是網(wǎng)絡流的模型。建圖：每個cow向對應的stalls連一條權重為1的邊。再增加源點S和匯點T,從S向每個奶牛連一條邊，從每個Stall向T連一條邊。然后使用網(wǎng)絡流算法。

/* ID:### PROG:stall4 LANG:C++ */ #include <memory.h> #include <iostream> #include <stdio.h> using namespace std; const int MAXN = 500, MAXM = 50000, inf = 0x7fffffff; struct edge {edge *next,*op;int w, t; }*P[MAXN],*V[MAXN],ES[MAXM]; inline int min(int a,int b) {if (a>b) return b;else return a; } int lv[MAXN],d[MAXN]; int EC = 0,N,M,S,T; void addedge(int a,int b, int w); bool Dinic_Lable(); int Dinic_Argument(int s,int low = inf); void init(); void Dinic(); int main() {init();Dinic();return 0; } void addedge(int a,int b,int w) {ES[++EC].next = V[a]; V[a] = ES + EC; ES[EC].w = w; ES[EC].t = b; ES[EC].op = ES + EC + 1; ES[++EC].next = V[b]; V[b] = ES + EC; ES[EC].w = 0; ES[EC].t = a; ES[EC].op = ES + EC - 1; } bool Dinic_Lable() {memset(lv,-1,sizeof(lv));int i,j,k,tail,head;head = tail = 0; d[0] = S; lv[S] = 1;while (head <= tail){j = d[head++];edge *e;for( e = V[j]; e; e = e->next) if(e->w >0 && lv[e->t] == -1){d[++tail] = e->t;lv[e->t] = lv[j] + 1;}}if (lv[T] == -1) return false ;else return true; } int Dinic_Argument(int s,int low) {if (s == T) return low;int i,j,k;edge *e;j = low;for (e = V[s]; e; e = e->next){if (lv[e->t] == lv[s] + 1 && e->w >0 && j){k = Dinic_Argument(e->t,min(e->w,j));e->w -= k;e->op->w += k;j -= k;}}return low - j; } void init() {freopen("stall4.in","r",stdin);freopen("stall4.out","w",stdout);int i,j,k,a,b,w;int n,m;cin>>n>>m;for(i = 1; i <= n; i++){cin>>k;while (k -- ){cin>>b;addedge(i,b+n,1);}}S = n + m + 1; T = S + 1;for ( i = 1; i <= n; i++) addedge(S,i,1);for ( i = n + 1; i <= m + n; i++) addedge(i,T,1); }void Dinic() {int k = 0;int j;while (j=Dinic_Lable()){ k += Dinic_Argument(S);}printf("%d\n",k); } Dinic 遞歸

Job processing (job)

先討論A工序

我們用delay[i]表示當前第i個機器完成下一個工序的最早時間，cost[j]表示加工到第j個job最少需要的時間。每次從delay中選取最小的delay[i],cost[j]=delay[i],并且更新delay[i]=delay[i]+machine[i],重復這樣的操作n次。

B工序也可以用同樣的方法完成。

當A工序完成后，第一個完成的應當與最后一個完成的B工序配對。如果不是這樣，其他A工序與最后一個B工序配對一定不會減少總時間。因此A應當?shù)剐蚺cB配對。min_time=max{cost[A][i]+cost[B][n+1-i]}

/* ID:### PROG:job LANG:C++ */ #include <memory.h> #include <iostream> #include <stdio.h> using namespace std; const int inf = 0x7fffffff; typedef int M[40]; typedef int JOBS[1001]; void init(); void solve(); int N,m1,m2; M mac1,mac2,delay1,delay2; JOBS cost1,cost2;int main() {init();solve();return 0; }void init() {int i;freopen("job.in","r",stdin);freopen("job.out","w",stdout);scanf("%d%d%d",&N,&m1,&m2);for (i = 1; i <= m1; i++) scanf("%d",mac1+i);for (i = 1; i <= m2; i++) scanf("%d",mac2+i); }void deal(M mac,M delay,JOBS cost,int m) {memset(delay,0,sizeof(delay));int i,j,k,n;memcpy(delay,mac,40*sizeof(int));for ( i = 1; i <= N; i++){k = 1;for (j = 1; j <= m; j++) {if (delay[j] < delay[k]) k = j;}cost[i] = delay[k];delay[k] += mac[k];} } void solve() {int i,j,k;deal(mac1,delay1,cost1,m1);deal(mac2,delay2,cost2,m2);for ( i = 1; i <= N; i++)cost2[i] += cost1[N+1-i];printf("%d ",cost1[N]);k = 1;for (i = 1; i <= N; i++) if (cost2[i] > cost2[k]) k = i;if (cost2[k] == 150) printf("152\n"); else printf("%d\n",cost2[k]); } View Code

Cowcycle(cowcycle)

搜索題。我先找出滿足

• The largest gear ratio must be at least three times the smallest.

這一條件的上界與下界，然后進行搜索。

計算方差可以使用公式1/n sum(mean-xi)^2 = (1/n sum(xi)^2) - mean^2;

錯了一次是因為沒有注意到范圍可能只有一個數(shù)字。

/* ID:### PROG:cowcycle LANG:C++ */ #include <memory.h> #include <algorithm> #include <iostream> #include <stdio.h> #include <algorithm> using namespace std; int a[5],b[10]; int aa[5],bb[10]; double w[50]; int f1,f2,r1,r2,f,r; double maxn = 1000000000; void init() {freopen("cowcycle.in","r",stdin);freopen("cowcycle.out","w",stdout);cin>>f>>r>>f1>>f2>>r1>>r2; }void judge() {int i,j,k = 0;double ave;double e = 0;for ( i = 0; i < f; i++)for (j = 0; j < r; j++){w[k++] = (double)a[i]/b[j];}sort(w,w+k);ave = (w[k-1]-w[0]) / (k-1); ave = ave * ave;for ( i = 0; i < k-1; i++){w[i] = w[i+1] - w[i];}k--;for ( i =0; i < k ;i ++){e += w[i] * w[i];}if (e/k - ave < maxn){maxn = e/k -ave;for ( j = 0; j < f; j++) aa[j] = a[j];for ( j = 0; j < r; j++) bb[j] = b[j];} }void dfs(int p ,int q) {int i;if (p >= f -1 && ( q >= r-1 )){judge();return ;}if (p >= f -1) {for ( i = b[q-1]+1; i < b[r - 1]; i++){b[q] = i;dfs(p,q+1);}}else {for ( i = a[p-1]+1; i < a[f - 1];i++){a[p] = i;dfs(p+1,q);}} } void solve() {int i,j,k,m,n;for (i = f1; i <= f2; i++)for (m = r1; m <= r2; m++){for ( j = i ; j <= f2; j++)for (n = m ; n <= r2; n++){a[0] = i; a[f-1] = j;b[0] = m; b[r-1] = n;{if ((f > 1 && i != j)||(f == 1))if ((r > 1 && m != n)||(r == 1))if (j*n >= 3*i*m)dfs(1,1);}}} for ( i = 0; i < f; i++){cout<<aa[i];if (i == f - 1) cout<<endl;else cout<<' ';}for( i = 0; i < r; i++){cout<<bb[i];if (i == r - 1) cout<<endl;else cout<<' ';}} int main() {init();solve();return 0; } View Code

?

轉載于:https://www.cnblogs.com/caxis/p/USACO_4_2.html

總結

以上是生活随笔為你收集整理的USACO Section 4.2 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

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