网络流n题
近日好不容易在自救之路寫完暑訓遺留下來的網絡流8題，在此回顧一下。
Going Home?POJ - 2195?
題意：m要去H，一個H只能容納一個m，一步一塊錢，問最小花費。
思路：最小費用最大流的板子題。有博客用了Dijkstra，不過在我看來，存在負權邊的圖是不能使用Dijkstra的，所以雖然我曾立誓再也不寫SPFA，現在也不得不屈服了。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 1024; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999999; 21 const int mod = 1000000007; 22 const double eps = 1e-6; 23 const double pi = acos(-1); 24 int n,m; 25 char mp[108][108]; 26 struct node 27 { 28 int x,y; 29 }p1[maxn],p2[maxn]; 30 int Head[maxn],Next[maxn*maxn],v[maxn*maxn],w[maxn*maxn],cap[maxn*maxn],cnt; 31 int t1,t2;int ans; 32 void init() 33 { 34 t1=1;cnt=t2=ans=0; 35 memset(Head,-1,sizeof(Head)); 36 } 37 38 void add(int x,int y,int z,int f){ 39 // cout<<x<<" "<<y<<" "<<z<<endl; 40 v[cnt]=y; 41 w[cnt]=z; 42 cap[cnt]=f; 43 Next[cnt]=Head[x]; 44 Head[x]=cnt++; 45 46 v[cnt]=x; 47 w[cnt]=-z; 48 cap[cnt]=0; 49 Next[cnt]=Head[y]; 50 Head[y]=cnt++; 51 } 52 bool vis[maxn]; 53 int dis[maxn]; 54 int prevv[maxn],preve[maxn]; 55 int s,t; 56 bool spfa() 57 { 58 queue<int>q; 59 memset(vis,0,sizeof(vis)); 60 for(int i=1;i<=t;i++){ 61 dis[i]=inf; 62 } 63 64 dis[s]=0; 65 q.push(s); 66 while(!q.empty()){ 67 int u=q.front(); 68 q.pop(); 69 vis[u]=false; 70 for(int k=Head[u];k!=-1;k=Next[k]){ 71 if(cap[k]&&dis[v[k]]>dis[u]+w[k]){ 72 dis[v[k]]=dis[u]+w[k]; 73 prevv[v[k]]=u; 74 preve[v[k]]=k; 75 76 if(!vis[v[k]]){ 77 vis[v[k]]=true; 78 q.push(v[k]); 79 } 80 } 81 } 82 } 83 if(dis[t]==inf){return false;} 84 else return true; 85 } 86 int min_cost_flow() 87 { 88 while(spfa()){ 89 for(int i=t;i!=s;i=prevv[i]){ 90 int k=preve[i]; 91 cap[k]-=1; 92 cap[k^1]+=1; 93 } 94 ans+=dis[t]; 95 } 96 97 } 98 99 int main() 100 { 101 // ios::sync_with_stdio(false); 102 // freopen("in.txt","r",stdin); 103 104 while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){ 105 init(); 106 for(int i=1;i<=n;i++){ 107 scanf("%s",mp[i]+1); 108 for(int j=1;j<=m;j++){ 109 if(mp[i][j]=='m'){p1[++t1]=node{i,j};} 110 else if(mp[i][j]=='H'){p2[++t2]=node{i,j};} 111 } 112 } 113 s=1;t=t1+t2+1; 114 for(int i=2;i<=t1;i++){ 115 add(s,i,0,1); 116 for(int j=1;j<=t2;j++){ 117 add(i,j+t1,abs(p1[i].x-p2[j].x)+abs(p1[i].y-p2[j].y),inf); 118 } 119 } 120 for(int i=1;i<=t2;i++){ 121 add(i+t1,t,0,1); 122 } 123 124 min_cost_flow(); 125 printf("%d\n",ans); 126 } 127 128 return 0; 129 } View Code?
Dining??POJ - 3281?
題意：給奶牛做了吃的和喝的，每一頭奶牛都只能接受某些吃的和喝的，問最多能滿足多少奶牛。
思路：拆點。奶牛只能吃一份也只能和一份，那就把它拆成兩點，之間的邊容量為一。食物和飲料不用擔心，從源點或匯點連邊的時候，控制邊權為1就可以限制沒份食物或飲料只被吃一次了。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 20086; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999999; 21 const int mod = 1000000007; 22 const double eps = 1e-6; 23 const double pi = acos(-1); 24 int n,F,D; 25 int Head[maxn],Next[maxn],v[maxn],w[maxn],cnt; 26 int s,t; 27 void init() 28 { 29 cnt=0; 30 memset(Head,-1,sizeof(Head)); 31 } 32 33 void add(int x,int y) 34 { 35 // cout<<x<<" "<<y<<endl; 36 v[cnt]=y; 37 Next[cnt]=Head[x]; 38 w[cnt]=1; 39 Head[x]=cnt++; 40 41 v[cnt]=x; 42 Next[cnt]=Head[y]; 43 w[cnt]=0; 44 Head[y]=cnt++; 45 } 46 47 int food(int x) 48 { 49 return 2*n+1+x; 50 } 51 52 int drink(int x) 53 { 54 return 2*n+1+F+x; 55 } 56 57 int nu1(int x) 58 { 59 return x+1; 60 } 61 62 int nu2(int x) 63 { 64 return x+n+1; 65 } 66 67 void build() 68 { 69 s=1;t=drink(D)+1; 70 for(int i=1;i<=F;i++){ 71 add(s,food(i)); 72 } 73 for(int i=1;i<=D;i++){ 74 add(drink(i),t); 75 } 76 for(int i=1;i<=n;i++){ 77 add(nu1(i),nu2(i)); 78 } 79 } 80 81 int vis[maxn],num[maxn]; 82 83 84 bool bfs() 85 { 86 memset(vis,0,sizeof(vis)); 87 for(int i=1;i<=2*n+1+F+D+8;i++){ 88 num[i]=Head[i]; 89 } 90 vis[s]=1; 91 queue<int>q; 92 q.push(s); 93 int r=0; 94 while(!q.empty()){ 95 int u=q.front(); 96 q.pop(); 97 int k=Head[u]; 98 while(k!=-1){ 99 if(!vis[v[k]]&&w[k]){ 100 vis[v[k]]=vis[u]+1; 101 q.push(v[k]); 102 } 103 k=Next[k]; 104 } 105 } 106 return vis[t]; 107 } 108 109 int dfs(int u,int f) 110 { 111 if(u==t){return f;} 112 int &k=num[u]; 113 int sum=0; 114 while(k!=-1){ 115 if(vis[v[k]]==vis[u]+1&&w[k]){ 116 int d=dfs(v[k],min(f,w[k])); 117 f-=d; 118 w[k]-=d; 119 w[k^1]+=d; 120 sum+=d; 121 } 122 k=Next[k]; 123 } 124 return sum; 125 } 126 127 int Dinic() 128 { 129 int ans=0; 130 while(bfs()){ 131 int f; 132 while((f=dfs(s,inf))>0){ 133 ans+=f; 134 } 135 } 136 return ans; 137 } 138 139 140 int main() 141 { 142 // ios::sync_with_stdio(false); 143 // freopen("in.txt","r",stdin); 144 init(); 145 scanf("%d%d%d",&n,&F,&D); 146 for(int i=1;i<=n;i++){ 147 int m1,m2; 148 scanf("%d%d",&m1,&m2); 149 int num; 150 for(int j=1;j<=m1;j++){ 151 scanf("%d",&num); 152 add(food(num),nu1(i)); 153 } 154 for(int j=1;j<=m2;j++){ 155 scanf("%d",&num); 156 add(nu2(i),drink(num)); 157 } 158 } 159 build(); 160 printf("%d\n",Dinic()); 161 return 0; 162 } View Code?
Power Network?POJ - 1459?
題意：有發電廠用來發電，有用戶用來用電，用中間商不賺差價，問電力的最大流量。
思路：好像也是一個板子題，就是輸入有些許麻煩。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 30086; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999999; 21 const int mod = 1000000007; 22 const double eps = 1e-6; 23 const double pi = acos(-1); 24 25 int n,np,nc,m; 26 int s,t; 27 int Head[maxn],Next[maxn],v[maxn],w[maxn],cnt; 28 29 void init() 30 { 31 s=n;t=n+1; 32 memset(Head,-1,sizeof(Head)); 33 cnt=0; 34 } 35 36 void add(int x,int y,int z) 37 { 38 // cout<<x<<" "<<y<<" "<<z<<endl; 39 if(x==y){return;} 40 v[cnt]=y; 41 w[cnt]=z; 42 Next[cnt]=Head[x]; 43 Head[x]=cnt++; 44 45 v[cnt]=x; 46 w[cnt]=0; 47 Next[cnt]=Head[y]; 48 Head[y]=cnt++; 49 } 50 51 char str[maxn]; 52 int vis[maxn],num[maxn]; 53 54 bool bfs() 55 { 56 memset(vis,0,sizeof(vis)); 57 for(int i=0;i<=t;i++){ 58 num[i]=Head[i]; 59 } 60 vis[s]=1; 61 queue<int>q; 62 q.push(s); 63 int r=0; 64 while(!q.empty()){ 65 int u=q.front(); 66 q.pop(); 67 int k=Head[u]; 68 while(k!=-1){ 69 if(!vis[v[k]]&&w[k]){ 70 vis[v[k]]=vis[u]+1; 71 q.push(v[k]); 72 } 73 k=Next[k]; 74 } 75 } 76 return vis[t]; 77 } 78 79 int dfs(int u,int f) 80 { 81 if(u==t){return f;} 82 int &k=num[u]; 83 int sum=0; 84 while(k!=-1){ 85 if(vis[v[k]]==vis[u]+1&&w[k]){ 86 int d=dfs(v[k],min(f,w[k])); 87 f-=d; 88 w[k]-=d; 89 w[k^1]+=d; 90 sum+=d; 91 } 92 k=Next[k]; 93 } 94 return sum; 95 } 96 97 int Dinic() 98 { 99 int ans=0; 100 while(bfs()){ 101 int f; 102 while((f=dfs(s,inf))>0){ 103 ans+=f; 104 } 105 } 106 return ans; 107 } 108 109 110 111 int main() 112 { 113 // ios::sync_with_stdio(false); 114 // freopen("in.txt","r",stdin); 115 116 while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF){ 117 init(); 118 for(int i=1;i<=m;i++){ 119 scanf("%s",str); 120 int len =strlen(str); 121 int j,num = 0; 122 int x,y,z; 123 for(j=1;j<len;j++){ 124 if(str[j]>='0'&&str[j]<='9'){num=num*10+str[j]-'0';} 125 else break; 126 } 127 x=num;num=0; 128 for(j++;j<len;j++){ 129 if(str[j]>='0'&&str[j]<='9'){num=num*10+str[j]-'0';} 130 else break; 131 } 132 y=num;num=0; 133 for(j++;j<len;j++){ 134 if(str[j]>='0'&&str[j]<='9'){num=num*10+str[j]-'0';} 135 else break; 136 } 137 z=num; 138 add(x,y,z); 139 } 140 141 142 for(int i=1;i<=np;i++){ 143 scanf("%s",str); 144 int len = strlen(str); 145 int j=0,x,y,num=0; 146 for(j++;j<len;j++){ 147 if(str[j]>='0'&&str[j]<='9'){num=num*10+str[j]-'0';} 148 else break; 149 } 150 x=num;num=0; 151 for(j++;j<len;j++){ 152 if(str[j]>='0'&&str[j]<='9'){num=num*10+str[j]-'0';} 153 else break; 154 } 155 y=num;num=0; 156 add(s,x,y); 157 } 158 for(int i=1;i<=nc;i++){ 159 scanf("%s",str); 160 int len = strlen(str); 161 int j=0,x,y,num=0; 162 for(j++;j<len;j++){ 163 if(str[j]>='0'&&str[j]<='9'){num=num*10+str[j]-'0';} 164 else break; 165 } 166 x=num;num=0; 167 for(j++;j<len;j++){ 168 if(str[j]>='0'&&str[j]<='9'){num=num*10+str[j]-'0';} 169 else break; 170 } 171 y=num;num=0; 172 add(x,t,y); 173 } 174 printf("%d\n",Dinic()); 175 } 176 177 return 0; 178 } View Code?
Escape??HDU - 3605
題意：有很多人想跑路了，可是他們都有自己想去的星球，每個星球也有自己的容量，問所有人是否都可以去到自己的想去的星球上。
思路：這個人很多，把相同目的地的人合在一起才行。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 500086; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999999; 21 const int mod = 1000000007; 22 const double eps = 1e-6; 23 const double pi = acos(-1); 24 25 int Head[2000],Next[maxn],v[maxn],w[maxn],cnt; 26 int n,m,s,t; 27 int vis[2000],num[2000]; 28 int sum[1228]; 29 void init() 30 { 31 s=1050+m+1;t=s+1; 32 memset(sum,0,sizeof(sum)); 33 for(int i=0;i<=t;i++){ 34 Head[i]=-1; 35 } 36 cnt=0; 37 } 38 void add(int x,int y,int z) 39 { 40 // cout<<x<<" "<<y<<" "<<z<<endl; 41 if(x==y){return;} 42 v[cnt]=y; 43 w[cnt]=z; 44 Next[cnt]=Head[x]; 45 Head[x]=cnt++; 46 47 v[cnt]=x; 48 w[cnt]=0; 49 Next[cnt]=Head[y]; 50 Head[y]=cnt++; 51 } 52 53 bool bfs() 54 { 55 memset(vis,0,sizeof(vis)); 56 for(int i=0;i<=t;i++){ 57 num[i]=Head[i]; 58 } 59 vis[s]=1; 60 queue<int>q; 61 q.push(s); 62 int r=0; 63 while(!q.empty()){ 64 int u=q.front(); 65 q.pop(); 66 int k=Head[u]; 67 while(k!=-1){ 68 if(!vis[v[k]]&&w[k]){ 69 vis[v[k]]=vis[u]+1; 70 q.push(v[k]); 71 } 72 k=Next[k]; 73 } 74 } 75 return vis[t]; 76 } 77 78 int dfs(int u,int f) 79 { 80 if(u==t){return f;} 81 int &k=num[u]; 82 int sum=0; 83 while(k!=-1){ 84 if(vis[v[k]]==vis[u]+1&&w[k]){ 85 int d=dfs(v[k],min(f,w[k])); 86 f-=d; 87 w[k]-=d; 88 w[k^1]+=d; 89 sum+=d; 90 } 91 k=Next[k]; 92 } 93 return sum; 94 } 95 96 int Dinic() 97 { 98 int ans=0; 99 while(bfs()){ 100 int f; 101 while((f=dfs(s,inf))>0){ 102 ans+=f; 103 } 104 } 105 return ans; 106 } 107 108 int plant(int x) 109 { 110 return x+1025; 111 } 112 113 int main() 114 { 115 // ios::sync_with_stdio(false); 116 // freopen("in.txt","r",stdin); 117 118 while(scanf("%d%d",&n,&m)!=EOF){ 119 init(); 120 for(int i=0;i<n;i++){ 121 int num = 0,x; 122 for(int j=0;j<m;j++){ 123 scanf("%d",&x); 124 num=num*2+x; 125 } 126 sum[num]++; 127 } 128 for(int i=0;i<1024;i++){ 129 add(s,i,sum[i]); 130 } 131 for(int i=0;i<1024;i++){ 132 if(sum[i]){ 133 int ss = i; 134 for(int j=m;j>=1;j--){ 135 if(ss&1){add(i,plant(j),inf);} 136 ss>>=1; 137 } 138 } 139 } 140 for(int i=1;i<=m;i++){ 141 int num = 0; 142 scanf("%d",&num); 143 add(plant(i),t,num); 144 } 145 if(Dinic()==n){printf("YES\n");} 146 else printf("NO\n"); 147 } 148 149 return 0; 150 } View Code?
ACM Computer Factory?POJ - 3436?
題意：造電腦了，每一個工廠有若干入廠狀態和一個出廠狀態，問整個系統的最大產量。
思路：枚舉，如果有某家工廠的某個入廠狀態和另一家工廠的出廠狀態相同，那就連一條邊。題目要求輸出路徑，整個在Dinic的DFS里面加記錄一下就行了，這個題是有SPJ的，所以可以寫的隨心一點
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 100086; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999999; 21 const int mod = 1000000007; 22 const double eps = 1e-6; 23 const double pi = acos(-1); 24 int p,n; 25 int vis[155],num[155]; 26 int Head[155],Next[maxn],v[maxn],w[maxn],cnt; 27 vector<int>num1[155]; 28 int num2[155]; 29 int s,t,flows; 30 void init() 31 { 32 memset(Head,-1,sizeof(Head)); 33 s=2*n+1;t=s+1; 34 } 35 void add(int x,int y,int z) 36 { 37 // cout<<x<<" "<<y<<" "<<z<<endl; 38 if(x==y){return;} 39 v[cnt]=y; 40 w[cnt]=z; 41 Next[cnt]=Head[x]; 42 Head[x]=cnt++; 43 44 v[cnt]=x; 45 w[cnt]=0; 46 Next[cnt]=Head[y]; 47 Head[y]=cnt++; 48 } 49 50 bool bfs() 51 { 52 53 memset(vis,0,sizeof(vis)); 54 for(int i=0;i<=t;i++){ 55 num[i]=Head[i]; 56 } 57 vis[s]=1; 58 queue<int>q; 59 q.push(s); 60 int r=0; 61 while(!q.empty()){ 62 int u=q.front(); 63 q.pop(); 64 int k=Head[u]; 65 while(k!=-1){ 66 if(!vis[v[k]]&&w[k]){ 67 vis[v[k]]=vis[u]+1; 68 q.push(v[k]); 69 } 70 k=Next[k]; 71 } 72 } 73 return vis[t]; 74 } 75 struct node 76 { 77 int u,v,w; 78 }; 79 queue<node>q; 80 int anss; 81 int dfs(int u,int f) 82 { 83 if(u==t){return f;} 84 int &k=num[u]; 85 int sum=0; 86 while(k!=-1){ 87 if(vis[v[k]]==vis[u]+1&&w[k]){ 88 int d=dfs(v[k],min(f,w[k])); 89 if(d>0){ 90 if(u!=s&&v[k]!=t&&u>n){ 91 q.push(node{u-n,v[k],d}); 92 anss++; 93 } 94 w[k]-=d; 95 w[k^1]+=d; 96 return d; 97 } 98 } 99 k=Next[k]; 100 } 101 return sum; 102 } 103 int Dinic() 104 { 105 int ans=0; 106 while(bfs()){ 107 int f; 108 while((f=dfs(s,inf))>0){ 109 ans+=f; 110 } 111 } 112 return ans; 113 } 114 int a[15]; 115 int u; 116 void num_dfs(int t,int ans) 117 { 118 if(t==p+1){ 119 num1[u].push_back(ans); 120 return; 121 } 122 if(a[t]==0){ 123 num_dfs(t+1,ans*2); 124 } 125 else if(a[t]==1){ 126 num_dfs(t+1,ans*2+1); 127 } 128 else{ 129 num_dfs(t+1,ans*2); 130 num_dfs(t+1,ans*2+1); 131 } 132 } 133 134 int sta(int x) 135 { 136 return x; 137 } 138 139 int endd(int x) 140 { 141 return x+n; 142 } 143 144 int main() 145 { 146 // ios::sync_with_stdio(false); 147 // freopen("in.txt","r",stdin); 148 149 scanf("%d%d",&p,&n); 150 init(); 151 for(int i=1;i<=n;i++){ 152 num1[i].clear();num2[i]=0; 153 } 154 for(int i=1;i<=n;i++){ 155 scanf("%d",&flows); 156 add(sta(i),endd(i),flows); 157 u=i; 158 for(int j=1;j<=p;j++){ 159 scanf("%d",&a[j]); 160 } 161 num_dfs(1,0); 162 for(int j=1;j<=p;j++){ 163 int h; 164 scanf("%d",&h); 165 num2[i]=num2[i]*2+h; 166 } 167 } 168 for(int i=1;i<=n;i++){ 169 int siz = num1[i].size(); 170 if(num2[i]==(1<<p)-1){ 171 add(endd(i),t,inf); 172 } 173 for(int j=0;j<siz;j++){ 174 if(num1[i][j]==0){add(s,sta(i),inf);} 175 for(int k=1;k<=n;k++){ 176 if(num1[i][j]==num2[k]){ 177 add(endd(k),sta(i),inf); 178 } 179 } 180 } 181 } 182 printf("%d ",Dinic()); 183 printf("%d\n",anss); 184 while(!q.empty()){ 185 printf("%d %d %d\n",q.front().u,q.front().v,q.front().w); 186 q.pop(); 187 } 188 return 0; 189 } View Code?
Minimum Cost?POJ - 2516
題意：有供貨源給商店老板供貨，每一種商品都有各自的對于每一個供應商都有其存儲量，對于每一個商店都有其需求量，對于每一對商店和供應商的組合，運輸都有其花費，求最大流量時的最大花費。
思路：每一種商品分別建圖，不然會TLE，因為邊太多了。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 400086; 19 const int inf = 2.1e9; 20 //const ll Inf = 999999999999999999; 21 //const int mod = 1000000007; 22 //const double eps = 1e-6; 23 //const double pi = acos(-1); 24 25 int n,m,k,ans; 26 int Head[5050*2],Next[maxn],v[maxn],cap[maxn],w[maxn],cnt; 27 bool vis[5050*2]; 28 int dis[5050*2]; 29 int prevv[5050*2]; 30 int preve[5050*2]; 31 int s,t,all; 32 void init() 33 { 34 s=0;t=2*k*(n+m)+1; 35 memset(Head,-1,sizeof(Head)); 36 ans=cnt=0; 37 } 38 39 int sshop(int x,int s) 40 { 41 return 2*k*(x-1)+s; 42 } 43 44 int eshop(int x,int y) 45 { 46 return sshop(x,y)+k; 47 } 48 49 int ssup(int x,int y) 50 { 51 return n*k*2+y+(x-1)*k*2; 52 } 53 54 int esup(int x,int y) 55 { 56 return ssup(x,y)+k; 57 } 58 59 void add(int x,int y,int z,int f){ 60 // cout<<x<<" "<<y<<" "<<z<<" "<<f<<endl; 61 v[cnt]=y; 62 w[cnt]=z; 63 cap[cnt]=f; 64 Next[cnt]=Head[x]; 65 Head[x]=cnt++; 66 67 v[cnt]=x; 68 w[cnt]=-z; 69 cap[cnt]=0; 70 Next[cnt]=Head[y]; 71 Head[y]=cnt++; 72 } 73 74 bool spfa(){ 75 queue<int>q; 76 memset(vis,0,sizeof(vis)); 77 for(int i=0;i<=t;i++){ 78 dis[i]=inf; 79 } 80 81 dis[s]=0; 82 q.push(s); 83 while(!q.empty()){ 84 int u=q.front(); 85 q.pop(); 86 vis[u]=false; 87 for(int k=Head[u];k!=-1;k=Next[k]){ 88 if(cap[k]&&dis[v[k]]>dis[u]+w[k]){ 89 dis[v[k]]=dis[u]+w[k]; 90 prevv[v[k]]=u; 91 preve[v[k]]=k; 92 93 if(!vis[v[k]]){ 94 vis[v[k]]=true; 95 q.push(v[k]); 96 } 97 } 98 } 99 } 100 if(dis[t]==inf){return false;} 101 else return true; 102 }int anss=0; 103 int min_cost_flow(){ 104 while(spfa()){ 105 anss++; 106 for(int i=t;i!=s;i=prevv[i]){ 107 int k=preve[i]; 108 cap[k]-=1; 109 cap[k^1]+=1; 110 } 111 ans+=dis[t]; 112 } 113 return ans; 114 } 115 116 int input1[105][105]; 117 int input2[105][105]; 118 119 120 121 void build(int kk) 122 { 123 init(); 124 for(int i=1;i<=n;i++){ 125 add(sshop(i,kk),eshop(i,kk),0,input1[i][kk]); 126 } 127 for(int i=1;i<=m;i++){ 128 add(ssup(i,kk),esup(i,kk),0,input2[i][kk]); 129 } 130 for(int i=1;i<=n;i++){ 131 add(s,sshop(i,kk),0,inf); 132 } 133 for(int i=1;i<=m;i++){ 134 add(esup(i,kk),t,0,inf); 135 } 136 } 137 138 int main() 139 { 140 // ios::sync_with_stdio(false); 141 // freopen("in.txt","r",stdin); 142 while(scanf("%d%d%d",&n,&m,&k)!=EOF&&(n||m||k)){ 143 init();all=0;anss=0; 144 for(int i=1;i<=n;i++){ 145 for(int j=1;j<=k;j++){ 146 int input; 147 scanf("%d",&input); 148 all+=input; 149 input1[i][j]=input; 150 } 151 } 152 153 for(int i=1;i<=m;i++){ 154 for(int j=1;j<=k;j++){ 155 int input; 156 scanf("%d",&input); 157 input2[i][j]=input; 158 } 159 } 160 int ans=0; 161 for(int i=1;i<=k;i++){ 162 build(i); 163 for(int j=1;j<=n;j++){ 164 for(int s=1;s<=m;s++){ 165 int input; 166 scanf("%d",&input); 167 add(eshop(j,i),ssup(s,i),input,inf); 168 } 169 } 170 ans+=min_cost_flow(); 171 } 172 if(anss!=all)ans=-1; 173 printf("%d\n",ans); 174 } 175 176 return 0; 177 } View Code?
Cyclic Tour??HDU - 1853?
題意：某個人要轉圈圈，每個點之走一次，問最小花費。
思路：把每個點拆開（pi1和pi2），有邊的話就建一條pi2到pj1的邊，源點到每個p1建邊容量為一，花費為0，匯點同理，然后網絡流即可。建圖雖然沒有體現環，但是如果網絡流跑滿了，就說明每個點都在環內了（每個點的出度和入度都是1）
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 100086; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999999; 21 const int mod = 1000000007; 22 const double eps = 1e-6; 23 const double pi = acos(-1); 24 int m,n,s,t,ans,anss; 25 int Head[308],Next[maxn],v[maxn],w[maxn],cap[maxn],cnt; 26 bool vis[308]; 27 int dis[308],prevv[308],preve[308]; 28 void init() 29 { 30 anss=0; 31 memset(Head,-1,sizeof(Head)); 32 s=0,t=2*n+1;ans=cnt=0; 33 } 34 void add(int x,int y,int z,int f){ 35 // cout<<x<<C" "<<y<<" "<<z<<" "<<f<<endl; 36 v[cnt]=y; 37 w[cnt]=z; 38 cap[cnt]=f; 39 Next[cnt]=Head[x]; 40 Head[x]=cnt++; 41 42 v[cnt]=x; 43 w[cnt]=-z; 44 cap[cnt]=0; 45 Next[cnt]=Head[y]; 46 Head[y]=cnt++; 47 } 48 49 bool spfa(){ 50 queue<int>q; 51 memset(vis,0,sizeof(vis)); 52 for(int i=0;i<=t;i++){ 53 dis[i]=inf; 54 } 55 56 dis[s]=0; 57 q.push(s); 58 while(!q.empty()){ 59 int u=q.front(); 60 q.pop(); 61 vis[u]=false; 62 for(int k=Head[u];k!=-1;k=Next[k]){ 63 if(cap[k]&&dis[v[k]]>dis[u]+w[k]){ 64 dis[v[k]]=dis[u]+w[k]; 65 prevv[v[k]]=u; 66 preve[v[k]]=k; 67 68 if(!vis[v[k]]){ 69 vis[v[k]]=true; 70 q.push(v[k]); 71 } 72 } 73 } 74 } 75 // fuck(dis[t]) 76 if(dis[t]==inf){return false;} 77 else return true; 78 } 79 int min_cost_flow(){ 80 while(spfa()){ 81 anss++; 82 for(int i=t;i!=s;i=prevv[i]){ 83 int k=preve[i]; 84 cap[k]-=1; 85 cap[k^1]+=1; 86 } 87 ans+=dis[t]; 88 } 89 // fuck(ans) 90 return ans; 91 } 92 93 int main() 94 { 95 // ios::sync_with_stdio(false); 96 // freopen("in.txt","r",stdin); 97 98 while(scanf("%d%d",&n,&m)!=EOF){ 99 init(); 100 for(int i=1;i<=m;i++){ 101 int x,y,z; 102 scanf("%d%d%d",&x,&y,&z); 103 add(x,y+n,z,1); 104 } 105 106 for(int i=1;i<=n;i++){ 107 add(i+n,t,0,1); 108 add(s,i,0,1); 109 } 110 int ans = min_cost_flow(); 111 if(anss!=n){ans=-1;} 112 printf("%d\n",ans); 113 } 114 115 116 117 return 0; 118 } View Code?
Fox And Dinner?CodeForces - 510E?
題意：n個數字，組成若干個環，相鄰的兩個數相加必須是質數，輸出組合方式。
思路：和上一題相同，就是跑滿之后才能看出來滿足題意。具體方法是，分為奇數和偶數，源點到奇數的權值為2，偶數到匯點的權值是2，如果相加為質數，奇數到偶數權值為1.跑滿的話，說明每個數旁邊都有兩個數，滿足題意。然后通過深搜找出途中的環。因為滿足題意，每個點只有兩個相鄰的點，所以可以無腦向下搜。注意網絡流途中的邊權變化，導致技術和偶數的有效邊權值是不一樣的。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 100086; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999999; 21 const int mod = 1000000007; 22 const double eps = 1e-6; 23 const double pi = acos(-1); 24 int n,s,t; 25 int nums[206]; 26 int vis[maxn],num[maxn]; 27 int prime[maxn],cur; 28 bool check[maxn]; 29 int Head[208],Next[maxn],v[maxn],w[maxn],cnt; 30 31 void init() 32 { 33 memset(Head,-1,sizeof(Head)); 34 cnt=0; 35 s=0,t=n+1; 36 } 37 38 void primes() 39 { 40 for(int i=2;i<20086;i++){ 41 if(!check[i]){ 42 prime[cur++]=i; 43 } 44 for(int j=0;j<cur;j++){ 45 if(i*prime[j]>20086){ 46 break; 47 } 48 check[i*prime[j]]=i; 49 if(i%prime[j]==0){ 50 break; 51 } 52 } 53 } 54 } 55 56 57 58 void add(int x,int y,int z) 59 { 60 // if(x!=s&&y!=t)cout<<x<<" "<<y<<" "<<z<<endl; 61 if(x==y){return;} 62 v[cnt]=y; 63 w[cnt]=z; 64 Next[cnt]=Head[x]; 65 Head[x]=cnt++; 66 67 v[cnt]=x; 68 w[cnt]=0; 69 Next[cnt]=Head[y]; 70 Head[y]=cnt++; 71 } 72 73 bool bfs() 74 { 75 memset(vis,0,sizeof(vis)); 76 for(int i=0;i<=t;i++){ 77 num[i]=Head[i]; 78 } 79 vis[s]=1; 80 queue<int>q; 81 q.push(s); 82 int r=0; 83 while(!q.empty()){ 84 int u=q.front(); 85 q.pop(); 86 int k=Head[u]; 87 while(k!=-1){ 88 if(!vis[v[k]]&&w[k]){ 89 vis[v[k]]=vis[u]+1; 90 q.push(v[k]); 91 } 92 k=Next[k]; 93 } 94 } 95 return vis[t]; 96 } 97 98 int dfs(int u,int f) 99 { 100 if(u==t){return f;} 101 int &k=num[u]; 102 int sum=0; 103 while(k!=-1){ 104 if(vis[v[k]]==vis[u]+1&&w[k]){ 105 int d=dfs(v[k],min(f,w[k])); 106 if(d>0){ 107 w[k]-=d; 108 w[k^1]+=d; 109 return d; 110 } 111 } 112 k=Next[k]; 113 } 114 return sum; 115 } 116 int Dinic() 117 { 118 int ans=0; 119 while(bfs()){ 120 int f; 121 while((f=dfs(s,inf))>0){ 122 ans+=f; 123 } 124 } 125 return ans; 126 } 127 stack<int>st; 128 void dfs(int t) 129 { 130 vis[t]=1; 131 st.push(t); 132 for(int k=Head[t];k!=-1;k=Next[k]){ 133 if(v[k]==0||v[k]==n+1){continue;} 134 if(vis[v[k]]){continue;} 135 if(nums[t]%2==0&&w[k]){dfs(v[k]);} 136 if(nums[t]%2==1&&!w[k]){dfs(v[k]);} 137 } 138 vis[t]=-1; 139 } 140 141 142 queue<int>q[208]; 143 int main() 144 { 145 // ios::sync_with_stdio(false); 146 // freopen("in.txt","r",stdin); 147 148 primes(); 149 scanf("%d",&n); 150 for(int i=1;i<=n;i++){ 151 scanf("%d",&nums[i]); 152 }init(); 153 for(int i=1;i<=n;i++){ 154 if(nums[i]&1){add(s,i,2);} 155 else{add(i,t,2);} 156 for(int j=i+1;j<=n;j++){ 157 if(!check[nums[i]+nums[j]]){ 158 if(nums[i]&1){add(i,j,1);} 159 else{add(j,i,1);} 160 } 161 } 162 } 163 if(Dinic()!=n){printf("Impossible\n");return 0;} 164 165 int numi = 0; 166 memset(vis,0,sizeof(vis)); 167 for(int i=1;i<=n;i++){ 168 if(!vis[i]){ 169 dfs(i);numi++; 170 while(!st.empty()){ 171 q[i].push(st.top()); 172 st.pop(); 173 } 174 } 175 } 176 printf("%d\n",numi); 177 for(int i=1;i<=n;i++){ 178 if(!q[i].empty()){ 179 printf("%d",q[i].size()); 180 while(!q[i].empty()){ 181 printf(" %d",q[i].front()); 182 q[i].pop(); 183 } 184 printf("\n"); 185 } 186 187 } 188 return 0; 189 } View Code?
以上8題全靠建圖+貼板子，建好了圖就完成了90%。
這就是暑訓的8題了。接下來還是暑訓網絡流的題，一共四題，不過被收錄到圖論專題中。
?
Ombrophobic Bovines?POJ - 2391
題意：有奶牛要去避難，有n個避難所，第i個避難所已經有了ai頭牛，可以容納bi頭牛，從第i個避難所到第j個避難所需要花費ti時間，所有奶牛同時出發，問最小花費的時間。
思路：我一開始想到的是使用最小費用最大流，把原來的ans+=dis[t]改成ans=max(ans,dis[t])即可，建圖方式就是拆點（設為拆成x,y吧），源點到xi容量為ai.費用為0，yi到匯點容量為bi，費用為0，如果i與j之間有邊，就建邊xi到yj，容量正無窮，花費為所需時間。但是這樣做是錯誤的，原因在于，最小費用最大流執行過程中，會優先選擇最短的路，也就是說，如果可以留在本地，那么牛一定會留下來，但這樣不是最優解，避難所如果是：
1 0
1 1
1 1
0 1
如果所有路徑距離都是1，那么其實每頭牛向下走一格才是最優解，而不是23的留在原地，1走到4.
所以這題的正解其實是最短路+二分+最大流。
至于為什么要拆點，我記得白書上說，如果要限制點的流量，那么便可以拆點，可是這里并沒有限制流量，那么為什么要拆點捏，實際上是因為，在二分建圖的過程中，小于mid的邊就被連上了，拆點了的話，可以保證從i到j的過程沒有經過其他的點，這樣的mid限制才有意義。這里的沒有經過其他的點，僅僅是指，在二分建圖過程中，實際上從邏輯上分析，牛肯定是要經過其他的點的。
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 100086; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999; 21 //const int mod = 1000000007; 22 //const double eps = 1e-6; 23 //const double pi = acos(-1); 24 ll mp[500][500]; 25 int Head[500],Next[maxn],v[maxn],cnt; 26 int vis[500],num[500]; 27 int num1[500],num2[maxn]; 28 ll w[maxn]; 29 int n,m,s,t; 30 ll all; 31 void init() 32 { 33 all= 0; 34 memset(Head,-1,sizeof(Head)); 35 cnt=0;s=0,t=n*2+1; 36 for(int i=1;i<=n;i++){ 37 for(int j=1;j<=n;j++){ 38 mp[i][j]=Inf; 39 } 40 } 41 } 42 43 void add(int x,int y,int z) 44 { 45 // cout<<x<<" "<<y<<" "<<z<<endl; 46 if(x==y){return;} 47 v[cnt]=y; 48 w[cnt]=z; 49 Next[cnt]=Head[x]; 50 Head[x]=cnt++; 51 52 v[cnt]=x; 53 w[cnt]=0; 54 Next[cnt]=Head[y]; 55 Head[y]=cnt++; 56 } 57 58 bool bfs() 59 { 60 memset(vis,0,sizeof(vis)); 61 for(int i=0;i<=t;i++){ 62 num[i]=Head[i]; 63 } 64 vis[s]=1; 65 queue<int>q; 66 q.push(s); 67 int r=0; 68 while(!q.empty()){ 69 int u=q.front(); 70 q.pop(); 71 int k=Head[u]; 72 while(k!=-1){ 73 if(!vis[v[k]]&&w[k]){ 74 vis[v[k]]=vis[u]+1; 75 q.push(v[k]); 76 } 77 k=Next[k]; 78 } 79 } 80 return vis[t]; 81 } 82 83 ll dfs(int u,ll f) 84 { 85 if(u==t){return f;} 86 int &k=num[u]; 87 ll sum=0; 88 while(k!=-1){ 89 if(vis[v[k]]==vis[u]+1&&w[k]){ 90 ll d=dfs(v[k],min(f,w[k])); 91 if(d>0){ 92 w[k]-=d; 93 w[k^1]+=d; 94 return d; 95 } 96 } 97 k=Next[k]; 98 } 99 return sum; 100 } 101 ll Dinic() 102 { 103 ll ans=0; 104 while(bfs()){ 105 ll f; 106 while((f=dfs(s,inf))>0){ 107 ans+=f; 108 } 109 } 110 return ans; 111 } 112 113 114 void floyd() 115 { 116 for(int k=1;k<=n;k++){ 117 for(int i=1;i<=n;i++){ 118 for(int j=1;j<=n;j++){ 119 mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); 120 } 121 } 122 } 123 } 124 125 void build(ll x) 126 { 127 t=n+1; 128 cnt=0;memset(Head,-1,sizeof(Head)); 129 for(int i=1;i<=n;i++){ 130 add(s,i,num1[i]); 131 add(i,t,num2[i]); 132 // add(i,i+n,inf); 133 } 134 for(int i=1;i<=n;i++){ 135 for(int j=i+1;j<=n;j++){ 136 if(mp[i][j]<=x){ 137 add(i,j,inf); 138 add(j,i,inf); 139 } 140 } 141 } 142 143 } 144 145 bool check(ll x) 146 { 147 build(x); 148 if(Dinic()==all){return true;} 149 return false; 150 } 151 152 int main() 153 { 154 // ios::sync_with_stdio(false); 155 // freopen("in.txt","r",stdin); 156 157 scanf("%d%d",&n,&m); 158 init(); 159 for(int i=1;i<=n;i++){ 160 scanf("%d%d",&num1[i],&num2[i]); 161 all+=num1[i]; 162 } 163 164 for(int i=1;i<=m;i++){ 165 int x,y; 166 ll z; 167 scanf("%d%d%lld",&x,&y,&z); 168 mp[x][y]=mp[y][x]=min(mp[y][x],z); 169 } 170 floyd(); 171 ll l=0,r=Inf,ans=-1; 172 while(r>=l){ 173 // fuck("______________") 174 ll mid=(r+l)/2; 175 if(check(mid)){r=mid-1;ans=mid;} 176 else l=mid+1; 177 } 178 if(ans==Inf){ans=-1;} 179 printf("%lld",ans); 180 181 return 0; 182 } View Code?
Budget?POJ - 2396
題意：就是給一個矩陣要滿足的條件，具體是每行之和，每列之和，以及每個數的大小限制，要求構建出一個矩陣。
思路：有上下界的網絡流。
明天我再單獨寫一篇博客紀念這題～～～～
1 #include<iostream> 2 #include<algorithm> 3 #include<vector> 4 #include<stack> 5 #include<queue> 6 #include<map> 7 #include<set> 8 #include<cstdio> 9 #include<cstring> 10 #include<cmath> 11 #include<ctime> 12 #define fuck(x) cout<<#x<<" = "<<x<<endl; 13 #define ls (t<<1) 14 #define rs ((t<<1)+1) 15 using namespace std; 16 typedef long long ll; 17 typedef unsigned long long ull; 18 const int maxn = 500086; 19 const int inf = 2.1e9; 20 const ll Inf = 999999999999999999; 21 const int mod = 1000000007; 22 const double eps = 1e-6; 23 const double pi = acos(-1); 24 25 int n,m,S,T,s,t; 26 int vis[maxn],num[maxn]; 27 int Head[maxn],Next[maxn],v[maxn],w[maxn],cnt; 28 int mp[505][505]; 29 int mph[505][505]; 30 int mpl[505][505]; 31 bool flag; 32 33 void init() 34 { 35 S=1;T=n+m+2;s=T+1;t=T+2; 36 memset(Head,-1,sizeof(Head)); 37 memset(mpl,0,sizeof(mpl)); 38 for(int i=1;i<505;i++){ 39 for(int j=1;j<505;j++){ 40 mph[i][j]=inf; 41 mp[i][j]=0; 42 } 43 } 44 cnt=0;flag=false; 45 } 46 47 void add(int x,int y,int z) 48 { 49 v[cnt]=y; 50 w[cnt]=z; 51 Next[cnt]=Head[x]; 52 Head[x]=cnt++; 53 54 v[cnt]=x; 55 w[cnt]=0; 56 Next[cnt]=Head[y]; 57 Head[y]=cnt++; 58 } 59 60 bool bfs() 61 { 62 memset(vis,0,sizeof(vis)); 63 for(int i=0;i<=t;i++){ 64 num[i]=Head[i]; 65 } 66 vis[s]=1; 67 queue<int>q; 68 q.push(s); 69 int r=0; 70 while(!q.empty()){ 71 int u=q.front(); 72 q.pop(); 73 int k=Head[u]; 74 while(k!=-1){ 75 if(!vis[v[k]]&&w[k]){ 76 vis[v[k]]=vis[u]+1; 77 q.push(v[k]); 78 } 79 k=Next[k]; 80 } 81 } 82 return vis[t]; 83 } 84 85 int dfs(int u,int f) 86 { 87 if(u==t){return f;} 88 int &k=num[u]; 89 int sum=0; 90 while(k!=-1){ 91 if(vis[v[k]]==vis[u]+1&&w[k]){ 92 int d=dfs(v[k],min(f,w[k])); 93 if(d>0){ 94 w[k]-=d; 95 w[k^1]+=d; 96 return d; 97 } 98 } 99 k=Next[k]; 100 } 101 return sum; 102 } 103 int Dinic() 104 { 105 int ans=0; 106 while(bfs()){ 107 int f; 108 while((f=dfs(s,inf))>0){ 109 ans+=f; 110 } 111 } 112 return ans; 113 } 114 115 int row(int x) 116 { 117 return x+1; 118 } 119 120 int col(int x) 121 { 122 return x+n+1; 123 } 124 125 int main() 126 { 127 int TT; 128 scanf("%d",&TT); 129 while(TT--){ 130 int all=0; 131 scanf("%d%d",&n,&m); 132 init(); 133 int x; 134 for(int i=1;i<=n;i++){ 135 scanf("%d",&x); 136 add(S,t,x);add(s,row(i),x);all+=x; 137 } 138 for(int j=1;j<=m;j++){ 139 scanf("%d",&x); 140 add(s,T,x); 141 add(col(j),t,x);all+=x; 142 } 143 add(T,S,inf); 144 int q; 145 scanf("%d",&q); 146 while(q--){ 147 int r,c,t; 148 char s[5]; 149 scanf("%d%d%s%d",&r,&c,s,&t); 150 151 if(r!=0&&c!=0){ 152 if(s[0]=='='){ 153 mpl[row(r)][col(c)]=max(mpl[row(r)][col(c)],t); 154 mph[row(r)][col(c)]=min(mph[row(r)][col(c)],t); 155 } 156 else if(s[0]=='>'){ 157 mpl[row(r)][col(c)]=max(mpl[row(r)][col(c)],t+1); 158 } 159 else if(s[0]=='<'){ 160 mph[row(r)][col(c)]=min(mph[row(r)][col(c)],t-1); 161 } 162 } 163 else if(r==0&&c!=0){ 164 for(int i=1;i<=n;i++){ 165 if(s[0]=='='){ 166 mpl[row(i)][col(c)]=max(mpl[row(i)][col(c)],t); 167 mph[row(i)][col(c)]=min(mph[row(i)][col(c)],t); 168 } 169 else if(s[0]=='>'){ 170 mpl[row(i)][col(c)]=max(mpl[row(i)][col(c)],t+1); 171 } 172 else if(s[0]=='<'){ 173 mph[row(i)][col(c)]=min(mph[row(i)][col(c)],t-1); 174 } 175 } 176 } 177 else if(r!=0&&c==0){ 178 for(int j=1;j<=m;j++){ 179 if(s[0]=='='){ 180 mpl[row(r)][col(j)]=max(mpl[row(r)][col(j)],t); 181 mph[row(r)][col(j)]=min(mph[row(r)][col(j)],t); 182 } 183 else if(s[0]=='>'){ 184 mpl[row(r)][col(j)]=max(mpl[row(r)][col(j)],t+1); 185 } 186 else if(s[0]=='<'){ 187 mph[row(r)][col(j)]=min(mph[row(r)][col(j)],t-1); 188 } 189 } 190 } 191 else{ 192 for(int i=1;i<=n;i++){ 193 for(int j=1;j<=m;j++){ 194 if(s[0]=='='){ 195 mpl[row(i)][col(j)]=max(mpl[row(i)][col(j)],t); 196 mph[row(i)][col(j)]=min(mph[row(i)][col(j)],t); 197 } 198 else if(s[0]=='>'){ 199 mpl[row(i)][col(j)]=max(mpl[row(i)][col(j)],t+1); 200 } 201 else if(s[0]=='<'){ 202 mph[row(i)][col(j)]=min(mph[row(i)][col(j)],t-1); 203 } 204 } 205 } 206 } 207 } 208 for(int i=row(1);i<=row(n);i++){ 209 for(int j=col(1);j<=col(m);j++){ 210 if(mpl[i][j]>mph[i][j]){flag=true;break;} 211 add(i,j,mph[i][j]-mpl[i][j]); 212 add(s,j,mpl[i][j]); 213 add(i,t,mpl[i][j]); 214 all+=mpl[i][j]; 215 } 216 } 217 if(flag){printf("IMPOSSIBLE\n\n");continue;} 218 219 int ans=Dinic(); 220 if(ans!=all){printf("IMPOSSIBLE\n\n");continue;} 221 for(int i=2;i<=n+1;i++){ 222 for(int k=Head[i];k!=-1;k=Next[k]){ 223 if(v[k]>=col(1)&&v[k]<=col(m)){ 224 mp[i-1][v[k]-n-1]+=w[k^1]+mpl[i][v[k]]; 225 } 226 } 227 } 228 for(int i=1;i<=n;i++){ 229 for(int j=1;j<m;j++){ 230 printf("%d ",mp[i][j]); 231 } 232 printf("%d\n",mp[i][m]); 233 } 234 printf("\n"); 235 } 236 return 0; 237 } View Code?
轉載于:https://www.cnblogs.com/ZGQblogs/p/10188207.html
總結
- 上一篇： 【Android开发】毛玻璃效果
- 下一篇： [From 10.1~10.5] 对象和