【題意】 有n<=200個恰好需要一天完成的任務，要求用最少的時間完成所有任務。任務可以同時完成。但是有一些約束，分有向和無向兩種，其中A-->B表示A必須在B前面完成，而A--B表示A和B不能在同一天完成。

?

題解：最具體的題解在紫書上。。。

如果樹上的所有邊都是有向邊，那么答案就是最長鏈上的點數(shù)。

這個顯然。。因為A-->B--->C---->D就最少需要四天。。

這樣，原問題轉(zhuǎn)化為：將樹上所有的無向邊定向，使得樹上的最長鏈最短。

最長鏈最短——二分答案。

現(xiàn)在問題再次轉(zhuǎn)化：給定一個x，判斷是否可以給無向邊定向，使得最長鏈的點數(shù)<=x。

?

設定f[i]表示以i為根的子樹全部定向后，最長鏈點數(shù)不超過x的前提下，后代到i的最長鏈的最小值。g[i]相反（i到后代）。

設y為i的某個孩子。

轉(zhuǎn)化無向邊的過程分為兩種情況：

a. 如果一個子樹中不存在無向邊，則經(jīng)過子樹的根結(jié)點的最長有向路結(jié)點數(shù)為f+g+1。

b. 如果一個結(jié)點a的子結(jié)點存在無向邊，則我們先遞歸求出所有a的子結(jié)點的f和g，然后暴力枚舉將所有無向邊轉(zhuǎn)化為上行/下行有向邊，對于每一種枚舉，按照上面不存在無向邊時的方法，求出f,? g和f+g+1，檢查是否大于k。枚舉的過程中，記下所有成功的枚舉中最小的f和g，把它們和原本就是有向邊子結(jié)點的最小的f和g比較，取較大值。（f和g本身是最長路的長度，這里要取的是不同成功的枚舉情況下，遇到的最小的f和g。）

?

如何給邊定向呢？

但是如果我們完全枚舉無向邊的轉(zhuǎn)換方法，則復雜度為O(2^n)，n為子結(jié)點中無向邊的數(shù)量。這里有一個非常棒的優(yōu)化：

求出所有子結(jié)點的f和g之后，把無向邊的f和g值存到一個數(shù)組中，按照f值排序。

之后我們從第一位開始考慮，將無向邊換為下行有向邊，考慮到第p位的時候，我們可以將前p-1位的無向邊一并換為下行有向邊。因為第p位的f值大于前p-1位無向邊的f值，將前p-1位同時換為下行有向邊，整個樹的f值不會變（f為最長路的長度，而排序后，前p-1位形成的路都不會比第p位長），而g值有可能變小。這時，我們找出第p+1位到第n位中最大的g值，求出f+g+1，檢查是否小于等于k即可。一旦有某一個p滿足了要求就可以得出結(jié)果并終止枚舉。復雜度為線性。

也就是說，我們只需要枚舉p，把f值前小的全部定向為y-->i。

求g的過程相同，按照g值排序、枚舉即可。

?

為什么取的是不同情況下遇到的最小的f和g呢？

因為對于以后要用到f[i]和g[i]的點，必定是i的父親，它每次只用到f[i]或g[i]。

但是對于根節(jié)點而言，它的最長鏈是f[i]+g[i]，這里的f[i]和g[i]取了不同的情況，所以我們在求f[i]、g[i]的時候就看ff+gg+1是否<=lim，是的話才更新。也就是說，如果沒有一種方案滿足，f[i]和g[i]都是INF。

所以最后判斷是否可行只需要看根節(jié)點的f[i]或g[i]是否<INF即可。

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 8 const int N=210,INF=(int)1e9; 9 int n,len,tl,f[N],g[N],first[N]; 10 struct node{ 11 int x,y,next,tmp; 12 bool bk; 13 }a[N]; 14 struct point{ 15 int d,id; 16 }tf[N],tg[N]; 17 18 int maxx(int x,int y){return x>y ? x:y;} 19 int minn(int x,int y){return x<y ? x:y;} 20 21 void ins(int x,int y,int tmp) 22 { 23 a[++len].x=x;a[len].y=y;a[len].tmp=tmp;a[len].bk=0; 24 a[len].next=first[x];first[x]=len; 25 } 26 27 bool cmp(point x,point y){return x.d<y.d;} 28 29 void dp(int x,int lim) 30 { 31 for(int i=first[x];i;i=a[i].next) dp(a[i].y,lim); 32 tl=0; 33 for(int i=first[x];i;i=a[i].next) 34 { 35 int y=a[i].y; 36 if(a[i].tmp==2) 37 { 38 tl++; 39 tf[tl].d=f[y];tf[tl].id=i; 40 tg[tl].d=g[y];tg[tl].id=i; 41 } 42 } 43 sort(tf+1,tf+1+tl,cmp); 44 sort(tg+1,tg+1+tl,cmp); 45 if(tl==0) 46 { 47 f[x]=0;g[x]=0; 48 for(int i=first[x];i;i=a[i].next) 49 { 50 int y=a[i].y; 51 if(a[i].tmp==1) f[x]=maxx(f[x],f[y]+1); 52 if(a[i].tmp==0) g[x]=maxx(g[x],g[y]+1); 53 if(f[x]+g[x]+1>lim) {f[x]=INF,g[x]=INF;break;} 54 } 55 if(!first[x]) f[x]=g[x]=INF;//debug 56 } 57 else 58 { 59 //find_f 60 f[x]=INF;g[x]=INF; 61 int ff,gg; 62 for(int k=0;k<=tl;k++) 63 { 64 ff=0;gg=0; 65 if(k>0) a[tf[k].id].bk=1; 66 for(int i=first[x];i;i=a[i].next) 67 { 68 int y=a[i].y; 69 if(a[i].tmp==1 || (a[i].tmp==2 && a[i].bk==1)) ff=maxx(ff,f[y]+1); 70 if(a[i].tmp==0 || (a[i].tmp==2 && a[i].bk==0)) gg=maxx(gg,g[y]+1); 71 } 72 if(ff+gg+1<=lim) f[x]=minn(f[x],ff); 73 } 74 for(int k=1;k<=tl;k++) a[tf[k].id].bk=0; 75 76 77 for(int k=0;k<=tl;k++) 78 { 79 ff=0;gg=0; 80 if(k>0) a[tg[k].id].bk=1; 81 for(int i=first[x];i;i=a[i].next) 82 { 83 int y=a[i].y; 84 if(a[i].tmp==1 || (a[i].tmp==2 && a[i].bk==0)) ff=maxx(ff,f[y]+1); 85 if(a[i].tmp==0 || (a[i].tmp==2 && a[i].bk==1)) gg=maxx(gg,g[y]+1); 86 } 87 if(ff+gg+1<=lim) g[x]=minn(g[x],gg); 88 } 89 for(int k=1;k<=tl;k++) a[tg[k].id].bk=0; 90 } 91 // printf("f %d = %d g %d = %d\n",x,f[x],x,g[x]); 92 } 93 94 bool check(int lim) 95 { 96 // printf("lim = %d\n",lim); 97 dp(1,lim); 98 return (f[1]<INF); 99 } 100 101 int main() 102 { 103 freopen("a.in","r",stdin); 104 int n,y; 105 char ch; 106 while(1) 107 { 108 n=0; 109 len=0; 110 memset(first,0,sizeof(first)); 111 while(1) 112 { 113 int x; 114 scanf("%d",&x); 115 if(x==0) break; 116 n=maxx(n,x); 117 while(1) 118 { 119 scanf("%d%c",&y,&ch); 120 n=maxx(n,y); 121 if(y==0) break; 122 if(ch=='d') ins(x,y,0); 123 else if(ch=='u') ins(x,y,1); 124 else ins(x,y,2); 125 } 126 } 127 if(n==0) break; 128 int l=0,r=n,mid;//debug 是n而不是n-1 129 while(l<r) 130 { 131 mid=(l+r)/2; 132 if(check(mid)) r=mid; 133 else l=mid+1; 134 } 135 printf("%d\n",l); 136 } 137 return 0; 138 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/KonjakJuruo/p/5969831.html

總結(jié)

以上是生活随笔為你收集整理的【uva1380 - 一个调度问题】思路题+树形dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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