二分图匹配
1 #include2 using namespace std; 3 bool vis[101]; 4 int match[101] , head[101] , cnt; 5 struct Edge{ 6 int end , upEd; 7 }Ed[10001]; 8 inline void add(int a , int b){ 9 Ed[++cnt].end = b; Ed[cnt].upEd = head[a]; head[a] = cnt;10 }11 bool dfs(int a){12 for(int i = head[a] ; i ; i = Ed[i].upEd)13 if(!vis[Ed[i].end]){14 vis[Ed[i].end] = 1;15 if(!match[Ed[i].end] || dfs(match[Ed[i].end])){16 match[Ed[i].end] = a;17 return 1;18 }19 }20 return 0;21 }22 int main(){23 int M , N , ans = 0 , a , b;24 scanf("%d%d%d%d" , &M , &N , &a , &b);25 while(a != -1){26 add(a , b - M);27 scanf("%d%d" , &a , &b);28 }29 for(int i = 1 ; i <= M ; i++){30 memset(vis , 0 , sizeof(vis));31 dfs(i);32 }33 for(int i = 1 ; i + M <= N ; i++) ans += (bool)match[i];34 if(ans == 0) cout << "No Solution!";35 else{36 cout << ans << endl;37 for(int i = 1 ; i + M <= N ; i++)38 if(match[i]) cout << match[i] << ' ' << i + M << endl;39 }40 return 0;41 }
环形均分纸牌
1 #include2 using namespace std; 3 inline int read(){ 4 int a = 0; 5 char c = getchar(); 6 while(!isdigit(c)) c = getchar(); 7 while(isdigit(c)) a = (a << 3) + (a << 1) + (c ^ '0') , c = getchar(); 8 return a; 9 }10 inline int abs(int a){11 return a > 0 ? a : -a;12 }13 long long S[1000001];14 int main(){15 int n = read();16 long long sum = 0;17 for(int i = 1 ; i <= n ; i++)18 sum += S[i] = read();19 sum /= n;20 for(int i = 1 ; i <= n ; i++)21 S[i] += S[i - 1] - sum;22 sort(S + 1 , S + n + 1);23 sum = 0;24 for(int i = 1 ; i <= n ; i++)25 sum += abs(S[i] - S[n + 1 >> 1]);26 printf("%lld" , sum);27 return 0;28 }
拆点二分图匹配/网络流，建图如下
1 #include2 #define MAXN 1050 3 using namespace std; 4 5 inline int read(){ 6 int a = 0; 7 char c = getchar(); 8 while(!isdigit(c)) 9 c = getchar(); 10 while(isdigit(c)){ 11 a = (a << 3) + (a << 1) + (c ^ '0'); 12 c = getchar(); 13 } 14 return a; 15 } 16 17 struct Edge{ 18 int end , upEd , flow; 19 }Ed[MAXN * MAXN << 1]; 20 int flo[MAXN] , now[MAXN] , head[MAXN] , N , K , M , cntEd = 1; 21 queue < int > q; 22 bool vis[MAXN]; 23 24 inline void addEd(int a , int b , int c){ 25 Ed[++cntEd].end = b; 26 Ed[cntEd].upEd = head[a]; 27 Ed[cntEd].flow = c; 28 head[a] = cntEd; 29 } 30 31 bool bfs(){ 32 while(!q.empty()) 33 q.pop(); 34 q.push(0); 35 memset(vis , 0 , sizeof(vis)); 36 vis[0] = flo[0] = 1; 37 while(!q.empty()){ 38 int t = q.front(); 39 q.pop(); 40 for(int i = head[t] ; i ; i = Ed[i].upEd) 41 if(!vis[Ed[i].end] && Ed[i].flow){ 42 vis[Ed[i].end] = 1; 43 flo[Ed[i].end] = flo[t] + 1; 44 if(Ed[i].end == N + K + 1){ 45 memcpy(now , head , sizeof(head)); 46 return 1; 47 } 48 q.push(Ed[i].end); 49 } 50 } 51 return 0; 52 } 53 54 bool Dinic(int dir){ 55 if(dir == N + K + 1) 56 return 1; 57 for(int &i = now[dir] ; i ; i = Ed[i].upEd) 58 if(flo[Ed[i].end] == flo[dir] + 1 && Ed[i].flow) 59 if(Dinic(Ed[i].end)){ 60 Ed[i].flow--; 61 Ed[i ^ 1].flow++; 62 return 1; 63 } 64 return 0; 65 } 66 67 void output(){ 68 for(int i = 1 ; i <= K ; i++){ 69 cout << i << ':'; 70 for(int j = head[i] ; j ; j = Ed[j].upEd) 71 if(Ed[j].end && !Ed[j].flow) 72 cout << ' ' << Ed[j].end - K; 73 cout << endl; 74 } 75 } 76 77 int main() 78 { 79 K = read(); 80 N = read(); 81 for(int i = 1 ; i <= K ; i++){ 82 int a = read(); 83 M += a; 84 addEd(0 , i , a); 85 addEd(i , 0 , 0); 86 } 87 for(int i = 1 ; i <= N ; i++){ 88 addEd(K + i , K + N + 1 , 1); 89 addEd(K + N + 1 , K + i , 0); 90 for(int j = read() ; j ; j--){ 91 int a = read(); 92 addEd(a , K + i , 1); 93 addEd(K + i , a , 0); 94 } 95 } 96 while(M && bfs()) 97 while(M && Dinic(0)) 98 M--; 99 if(M)100 cout << "No Solution!";101 else102 output();103 return 0;104 }
二分图带权最大独立集=总权值-二分图最小点集覆盖=总权值-最小割=总权值-最大流
注意格子之间的边不能正反都建无穷流（这代表的是无向图，在这里WA了两发还没看出来）
1 #include2 #define INF 0x3f3f3f3f 3 #define MAXN 10010 4 using namespace std; 5 6 inline int read(){ 7 int a = 0; 8 char c = getchar(); 9 while(!isdigit(c)) 10 c = getchar(); 11 while(isdigit(c)){ 12 a = (a << 3) + (a << 1) + (c ^ '0'); 13 c = getchar(); 14 } 15 return a; 16 } 17 18 struct Edge{ 19 int end , upEd , flow; 20 }Ed[MAXN << 2]; 21 int head[MAXN] , flo[MAXN] , now[MAXN] , M , N , ans , cntEd = 1; 22 queue < int > q; 23 bool vis[MAXN]; 24 25 inline void addEd(int a , int b , int c){ 26 Ed[++cntEd].end = b; 27 Ed[cntEd].upEd = head[a]; 28 Ed[cntEd].flow = c; 29 head[a] = cntEd; 30 } 31 32 bool bfs(){ 33 while(!q.empty()) 34 q.pop(); 35 q.push(0); 36 memset(vis , 0 , sizeof(vis)); 37 vis[0] = flo[0] = 1; 38 while(!q.empty()){ 39 int t = q.front(); 40 q.pop(); 41 for(int i = head[t] ; i ; i = Ed[i].upEd) 42 if(!vis[Ed[i].end] && Ed[i].flow){ 43 vis[Ed[i].end] = 1; 44 flo[Ed[i].end] = flo[t] + 1; 45 if(Ed[i].end == N * M + 1){ 46 memcpy(now , head , sizeof(head)); 47 return 1; 48 } 49 q.push(Ed[i].end); 50 } 51 } 52 return 0; 53 } 54 55 int Dinic(int dir , int minN){ 56 if(dir == N * M + 1) 57 return minN; 58 for(int &i = now[dir] ; i ; i = Ed[i].upEd) 59 if(Ed[i].flow && flo[Ed[i].end] == flo[dir] + 1){ 60 int t = Dinic(Ed[i].end , min(minN , Ed[i].flow)); 61 if(t){ 62 Ed[i].flow -= t; 63 Ed[i ^ 1].flow += t; 64 return t; 65 } 66 } 67 return 0; 68 } 69 70 int main(){ 71 M = read(); 72 N = read(); 73 for(int i = 0 ; i < M ; i++) 74 for(int j = 1 ; j <= N ; j++){ 75 int a = read(); 76 ans += a; 77 if(i + j & 1){ 78 addEd(0 , i * N + j , a); 79 addEd(i * N + j , 0 , 0); 80 if(i < M - 1){ 81 addEd(i * N + j , (i + 1) * N + j , INF); 82 addEd((i + 1) * N + j , i * N + j , 0); 83 } 84 if(j < N){ 85 addEd(i * N + j , i * N + j + 1 , INF); 86 addEd(i * N + j + 1 , i * N + j , 0); 87 } 88 if(i){ 89 addEd(i * N + j , (i - 1) * N + j , INF); 90 addEd((i - 1) * N + j , i * N + j , 0); 91 } 92 if(j - 1){ 93 addEd(i * N + j , i * N + j - 1 , INF); 94 addEd(i * N + j - 1 , i * N + j , 0); 95 } 96 } 97 else{ 98 addEd(i * N + j , N * M + 1 , a); 99 addEd(N * M + 1 , i * N + j , 0);100 }101 102 }103 int K;104 while(bfs())105 while(K = Dinic(0 , INF))106 ans -= K;107 cout << ans;108 return 0;109 }
注意到这是一个有上下界网络流
拆点，每一天对应两个点：早上和晚上
连边如下：
$S$向每一天晚上连$need_i$流量、$0$费用边表示当天多出了$need_i$块脏餐巾
每一天早上向$T$连$need_i$流量、$0$费用边表示当天需要$need_i$块干净餐巾
$S$向第一天早上连$(INF,p)$边表示购买
$i$天早上向$i+1$天早上连$(INF,0)$表示干净的餐巾可以存下来
然后晚上向对应的早上连清洗的时间和费用就行了
一定不能把边建成$S->$早上$->$晚上$->T$，因为这种连边方式没有限制下界
1 #include2 #define INF 0x7fffffff 3 #define int long long 4 //This code is written by Itst 5 using namespace std; 6 7 inline int read(){ 8 int a = 0; 9 char c = getchar(); 10 bool f = 0; 11 while(!isdigit(c) && c != EOF){ 12 if(c == '-') 13 f = 1; 14 c = getchar(); 15 } 16 if(c == EOF) 17 exit(0); 18 while(isdigit(c)){ 19 a = (a << 3) + (a << 1) + (c ^ '0'); 20 c = getchar(); 21 } 22 return f ? -a : a; 23 } 24 25 const int MAXN = 4010 , MAXM = 30010; 26 struct Edge{ 27 int end , upEd , f , c; 28 }Ed[MAXM]; 29 int head[MAXN] , dis[MAXN] , pre[MAXN] , flo[MAXN] , need[MAXN]; 30 int N , p , m , f , n , s , S , T , cntEd = 1; 31 bool vis[MAXN]; 32 queue < int > q; 33 34 inline void addEd(int a , int b , int c , int d = 0){ 35 Ed[++cntEd].end = b; 36 Ed[cntEd].upEd = head[a]; 37 Ed[cntEd].f = c; 38 Ed[cntEd].c = d; 39 head[a] = cntEd; 40 } 41 42 inline bool SPFA(){ 43 memset(dis , 0x3f , sizeof(dis)); 44 dis[S] = 0; 45 while(!q.empty()) 46 q.pop(); 47 q.push(S); 48 flo[S] = INF; 49 while(!q.empty()){ 50 int t = q.front(); 51 q.pop(); 52 vis[t] = 0; 53 for(int i = head[t] ; i ; i = Ed[i].upEd) 54 if(Ed[i].f && dis[Ed[i].end] > dis[t] + Ed[i].c){ 55 dis[Ed[i].end] = dis[t] + Ed[i].c; 56 flo[Ed[i].end] = min(Ed[i].f , flo[t]); 57 pre[Ed[i].end] = i; 58 if(!vis[Ed[i].end]){ 59 vis[Ed[i].end] = 1; 60 q.push(Ed[i].end); 61 } 62 } 63 } 64 return dis[T] != dis[T + 1]; 65 } 66 67 void input(){ 68 N = read(); 69 for(int i = 1 ; i <= N ; ++i) 70 need[i] = read(); 71 p = read(); 72 m = read(); 73 f = read(); 74 n = read(); 75 s = read(); 76 } 77 78 void init(){ 79 S = 0; 80 T = 2 * N + 1; 81 addEd(S , 1 , INF , p); 82 addEd(1 , S , 0 , -p); 83 for(int i = 1 ; i <= N ; ++i){ 84 addEd(i , T , need[i]); 85 addEd(T , i , 0); 86 addEd(S , i + N , need[i]); 87 addEd(i + N , S , 0); 88 } 89 for(int i = 1 ; i < N ; ++i){ 90 addEd(i , i + 1 , INF); 91 addEd(i + 1 , i , 0); 92 } 93 for(int i = 1 ; i + m <= N ; ++i){ 94 addEd(i + N , i + m , INF , f); 95 addEd(i + m , i + N , 0 , -f); 96 } 97 for(int i = 1 ; i + n <= N ; ++i){ 98 addEd(i + N , i + n , INF , s); 99 addEd(i + n , i + N , 0 , -s);100 }101 }102 103 void work(){104 int ans = 0;105 while(SPFA()){106 int cur = T , sum = 0;107 while(cur != S){108 Ed[pre[cur]].f -= flo[T];109 Ed[pre[cur] ^ 1].f += flo[T];110 sum += Ed[pre[cur]].c;111 cur = Ed[pre[cur] ^ 1].end;112 }113 ans += sum * flo[T];114 }115 cout << ans;116 }117 118 signed main(){119 #ifndef ONLINE_JUDGE120 freopen("in" , "r" , stdin);121 //freopen("out" , "w" , stdout);122 #endif123 input();124 init();125 work();126 return 0;127 }
最大权闭合子图
输出方案时满足能从$S$到达某一个点就表示这一个点被选中了
1 #include2 #define INF 0x7fffffff 3 //This code is written by Itst 4 using namespace std; 5 6 const int MAXN = 110 , MAXM = 25010; 7 struct Edge{ 8 int end , upEd , f , c; 9 }Ed[MAXM]; 10 int head[MAXN] , cur[MAXN] , dep[MAXN]; 11 int N , M , S , T , cntEd = 1 , ans; 12 bool vis[MAXN]; 13 queue < int > q; 14 15 inline void addEd(int a , int b , int c , int d = 0){ 16 Ed[++cntEd].end = b; 17 Ed[cntEd].upEd = head[a]; 18 Ed[cntEd].f = c; 19 Ed[cntEd].c = d; 20 head[a] = cntEd; 21 } 22 23 inline bool bfs(){ 24 while(!q.empty()) 25 q.pop(); 26 q.push(S); 27 memset(dep , 0 , sizeof(dep)); 28 dep[S] = 1; 29 while(!q.empty()){ 30 int t = q.front(); 31 q.pop(); 32 for(int i = head[t] ; i ; i = Ed[i].upEd) 33 if(Ed[i].f && !dep[Ed[i].end]){ 34 dep[Ed[i].end] = dep[t] + 1; 35 if(Ed[i].end == T){ 36 memcpy(cur , head , sizeof(head)); 37 return 1; 38 } 39 q.push(Ed[i].end); 40 } 41 } 42 return 0; 43 } 44 45 inline int dfs(int x , int mF){ 46 if(x == T) 47 return mF; 48 int sum = 0; 49 for(int &i = cur[x] ; i ; i = Ed[i].upEd) 50 if(Ed[i].f && dep[Ed[i].end] == dep[x] + 1){ 51 int t = dfs(Ed[i].end , min(mF - sum , Ed[i].f)); 52 if(t){ 53 Ed[i].f -= t; 54 Ed[i ^ 1].f += t; 55 sum += t; 56 if(sum == mF) 57 break; 58 } 59 } 60 return sum; 61 } 62 63 void input(){ 64 cin >> N >> M; 65 S = 0; 66 T = N + M + 1; 67 string s; 68 stringstream ss; 69 getline(cin , s); 70 for(int i = 1 ; i <= N ; ++i){ 71 ss.clear(); 72 getline(cin , s); 73 ss.str(s); 74 int K; 75 ss >> K; 76 ans += K; 77 addEd(S , i , K); 78 addEd(i , S , 0); 79 while(ss >> K){ 80 addEd(i , N + K , INF); 81 addEd(N + K , i , 0); 82 } 83 } 84 for(int i = 1 ; i <= M ; ++i){ 85 int a; 86 cin >> a; 87 addEd(i + N , T , a); 88 addEd(T , i + N , 0); 89 } 90 } 91 92 void work(){ 93 while(bfs()) 94 ans -= dfs(S , INF); 95 for(int i = head[S] ; i ; i = Ed[i].upEd) 96 if(dep[Ed[i].end]) 97 cout << Ed[i].end << ' '; 98 cout << endl; 99 for(int i = head[T] ; i ; i = Ed[i].upEd)100 if(dep[Ed[i].end])101 cout << Ed[i].end - N << ' ';102 cout << endl << ans;103 }104 105 int main(){106 #ifndef ONLINE_JUDGE107 freopen("in" , "r" , stdin);108 //freopen("out" , "w" , stdout);109 #endif110 input();111 work();112 return 0;113 }
状压最短路
1 #include2 //This code is written by Itst 3 using namespace std; 4 5 int dp[1 << 20] , T[110] , B[110][2] , F[110][2] , N , M; 6 queue < int > q; 7 bool vis[1 << 20]; 8 9 void input(){10 ios::sync_with_stdio(0);11 cin.tie(0);12 cin >> N >> M;13 string s;14 for(int i = 1 ; i <= M ; ++i){15 cin >> T[i] >> s;16 for(int j = 0 ; j < N ; ++j)17 if(s[j] == '+')18 B[i][0] |= 1 << j;19 else20 if(s[j] == '-')21 B[i][1] |= 1 << j;22 cin >> s;23 for(int j = 0 ; j < N ; ++j)24 if(s[j] == '-')25 F[i][0] |= 1 << j;26 else27 if(s[j] == '+')28 F[i][1] |= 1 << j;29 }30 }31 32 void work(){33 memset(dp , 0x7f , sizeof(dp));34 dp[(1 << N) - 1] = 0;35 q.push((1 << N) - 1);36 while(!q.empty()){37 int t = q.front();38 q.pop();39 vis[t] = 0;40 for(int j = 1 ; j <= M ; ++j)41 if((t & B[j][0]) == B[j][0] && !(t & B[j][1])){42 int k = (t ^ (t & F[j][0])) | F[j][1];43 if(dp[k] > dp[t] + T[j]){44 dp[k] = dp[t] + T[j];45 if(!vis[k]){46 vis[k] = 1;47 q.push(k);48 }49 }50 }51 }52 }53 54 void output(){55 cout << (dp[0] == 0x7f7f7f7f ? 0 : dp[0]);56 }57 58 int main(){59 #ifndef ONLINE_JUDGE60 freopen("in" , "r" , stdin);61 //freopen("out" , "w" , stdout);62 #endif63 input();64 work();65 output();66 return 0;67 }
二分图最大/小权匹配裸题
1 #include2 #define INF 0x7fffffff 3 //This code is written by Itst 4 using namespace std; 5 6 inline int read(){ 7 int a = 0; 8 char c = getchar(); 9 bool f = 0; 10 while(!isdigit(c) && c != EOF){ 11 if(c == '-') 12 f = 1; 13 c = getchar(); 14 } 15 if(c == EOF) 16 exit(0); 17 while(isdigit(c)){ 18 a = (a << 3) + (a << 1) + (c ^ '0'); 19 c = getchar(); 20 } 21 return f ? -a : a; 22 } 23 24 const int MAXN = 210 , MAXM = 21010; 25 struct Edge{ 26 int end , upEd , f , c; 27 }Ed[MAXM]; 28 int head[MAXN] , c[MAXN][MAXN] , dis[MAXN] , pre[MAXN]; 29 int N , S , T , cntEd = 1; 30 bool vis[MAXN]; 31 queue < int > q; 32 33 inline void addEd(int a , int b , int c , int d = 0){ 34 Ed[++cntEd].end = b; 35 Ed[cntEd].upEd = head[a]; 36 Ed[cntEd].f = c; 37 Ed[cntEd].c = d; 38 head[a] = cntEd; 39 } 40 41 inline bool SPFA(){ 42 memset(dis , 0x3f , sizeof(dis)); 43 dis[S] = 0; 44 while(!q.empty()) 45 q.pop(); 46 q.push(S); 47 while(!q.empty()){ 48 int t = q.front(); 49 q.pop(); 50 vis[t] = 0; 51 for(int i = head[t] ; i ; i = Ed[i].upEd) 52 if(Ed[i].f && dis[Ed[i].end] > dis[t] + Ed[i].c){ 53 dis[Ed[i].end] = dis[t] + Ed[i].c; 54 pre[Ed[i].end] = i; 55 if(!vis[Ed[i].end]){ 56 vis[Ed[i].end] = 1; 57 q.push(Ed[i].end); 58 } 59 } 60 } 61 return dis[T] != 0x3f3f3f3f; 62 } 63 64 void input(){ 65 N = read(); 66 T = N * 2 + 1; 67 for(int i = 1 ; i <= N ; ++i) 68 for(int j = 1 ; j <= N ; ++j) 69 c[i][j] = read(); 70 } 71 72 void init(int x){ 73 cntEd = 1; 74 memset(head , 0 , sizeof(head)); 75 for(int i = 1 ; i <= N ; ++i) 76 for(int j = 1 ; j <= N ; ++j){ 77 addEd(i , j + N , 1 , c[i][j] * x); 78 addEd(j + N , i , 0 , c[i][j] * -x); 79 } 80 for(int i = 1 ; i <= N ; ++i){ 81 addEd(S , i , 1); 82 addEd(i , S , 0); 83 addEd(i + N , T , 1); 84 addEd(T , i + N , 0); 85 } 86 } 87 88 void work(){ 89 init(1); 90 int ans = 0; 91 while(SPFA()){ 92 int cur = T , sum = 0; 93 while(cur != S){ 94 sum += Ed[pre[cur]].c; 95 --Ed[pre[cur]].f; 96 ++Ed[pre[cur] ^ 1].f; 97 cur = Ed[pre[cur] ^ 1].end; 98 } 99 ans += sum;100 }101 cout << ans << endl;102 init(-1);103 ans = 0;104 while(SPFA()){105 int cur = T , sum = 0;106 while(cur != S){107 sum += Ed[pre[cur]].c;108 --Ed[pre[cur]].f;109 ++Ed[pre[cur] ^ 1].f;110 cur = Ed[pre[cur] ^ 1].end;111 }112 ans += sum;113 }114 cout << -ans;115 }116 117 int main(){118 #ifndef ONLINE_JUDGE119 freopen("in" , "r" , stdin);120 //freopen("out" , "w" , stdout);121 #endif122 input();123 work();124 return 0;125 }
同试题库问题
1 #include2 #define INF 0x7fffffff 3 //This code is written by Itst 4 using namespace std; 5 6 inline int read(){ 7 int a = 0; 8 char c = getchar(); 9 bool f = 0; 10 while(!isdigit(c) && c != EOF){ 11 if(c == '-') 12 f = 1; 13 c = getchar(); 14 } 15 if(c == EOF) 16 exit(0); 17 while(isdigit(c)){ 18 a = (a << 3) + (a << 1) + (c ^ '0'); 19 c = getchar(); 20 } 21 return f ? -a : a; 22 } 23 24 const int MAXN = 510 , MAXM = 100010; 25 struct Edge{ 26 int end , upEd , f , c; 27 }Ed[MAXM]; 28 int head[MAXN] , cur[MAXN] , dep[MAXN]; 29 int N , M , S , T , cntEd = 1 , sum; 30 bool vis[MAXN]; 31 queue < int > q; 32 33 inline void addEd(int a , int b , int c , int d = 0){ 34 Ed[++cntEd].end = b; 35 Ed[cntEd].upEd = head[a]; 36 Ed[cntEd].f = c; 37 Ed[cntEd].c = d; 38 head[a] = cntEd; 39 } 40 41 inline bool bfs(){ 42 while(!q.empty()) 43 q.pop(); 44 q.push(S); 45 memset(dep , 0 , sizeof(dep)); 46 dep[S] = 1; 47 while(!q.empty()){ 48 int t = q.front(); 49 q.pop(); 50 for(int i = head[t] ; i ; i = Ed[i].upEd) 51 if(Ed[i].f && !dep[Ed[i].end]){ 52 dep[Ed[i].end] = dep[t] + 1; 53 if(Ed[i].end == T){ 54 memcpy(cur , head , sizeof(head)); 55 return 1; 56 } 57 q.push(Ed[i].end); 58 } 59 } 60 return 0; 61 } 62 63 inline int dfs(int x , int mF){ 64 if(x == T) 65 return mF; 66 int sum = 0; 67 for(int &i = cur[x] ; i ; i = Ed[i].upEd) 68 if(Ed[i].f && dep[Ed[i].end] == dep[x] + 1){ 69 int t = dfs(Ed[i].end , min(mF - sum , Ed[i].f)); 70 if(t){ 71 Ed[i].f -= t; 72 Ed[i ^ 1].f += t; 73 sum += t; 74 if(sum == mF) 75 break; 76 } 77 } 78 return sum; 79 } 80 81 void input(){ 82 M = read(); 83 N = read(); 84 T = N + M + 1; 85 for(int i = 1 ; i <= M ; ++i){ 86 int a = read(); 87 addEd(S , i , a); 88 addEd(i , S , 0); 89 sum += a; 90 } 91 for(int i = 1 ; i <= N ; ++i){ 92 addEd(i + M , T , read()); 93 addEd(T , i + M , 0); 94 } 95 for(int i = 1 ; i <= M ; ++i) 96 for(int j = 1 ; j <= N ; ++j){ 97 addEd(i , j + M , 1); 98 addEd(j + M , i , 0); 99 }100 }101 102 void work(){103 while(bfs())104 sum -= dfs(S , INF);105 if(sum)106 puts("0");107 else{108 puts("1");109 for(int i = 1 ; i <= M ; ++i){110 for(int j = head[i] ; j ; j = Ed[j].upEd)111 if(Ed[j].end && !Ed[j].f)112 cout << Ed[j].end - M << ' ';113 putchar('\n');114 }115 }116 }117 118 int main(){119 #ifndef ONLINE_JUDGE120 freopen("in" , "r" , stdin);121 //freopen("out" , "w" , stdout);122 #endif123 input();124 work();125 return 0;126 }
每一条边对应一个流量为$1$、费用为其价值的边和一条流量为$INF$、费用为$0$的边，然后最大费用最大流
1 #include2 #define INF 0x7fffffff 3 #define id(i , j) ((i) * (M + 1) + (j) + 1) 4 //This code is written by Itst 5 using namespace std; 6 7 inline int read(){ 8 int a = 0; 9 char c = getchar(); 10 bool f = 0; 11 while(!isdigit(c) && c != EOF){ 12 if(c == '-') 13 f = 1; 14 c = getchar(); 15 } 16 if(c == EOF) 17 exit(0); 18 while(isdigit(c)){ 19 a = (a << 3) + (a << 1) + (c ^ '0'); 20 c = getchar(); 21 } 22 return f ? -a : a; 23 } 24 25 const int MAXN = 1010 , MAXM = 20010; 26 struct Edge{ 27 int end , upEd , f , c; 28 }Ed[MAXM]; 29 int head[MAXN] , dis[MAXN] , pre[MAXN] , flo[MAXN]; 30 int N , M , a , b , S , T , cntEd = 1; 31 bool vis[MAXN]; 32 queue < int > q; 33 34 inline void addEd(int a , int b , int c , int d = 0){ 35 Ed[++cntEd].end = b; 36 Ed[cntEd].upEd = head[a]; 37 Ed[cntEd].f = c; 38 Ed[cntEd].c = d; 39 head[a] = cntEd; 40 } 41 42 inline bool SPFA(){ 43 memset(dis , -0x3f , sizeof(dis)); 44 dis[S] = 0; 45 while(!q.empty()) 46 q.pop(); 47 q.push(S); 48 flo[S] = INF; 49 while(!q.empty()){ 50 int t = q.front(); 51 q.pop(); 52 vis[t] = 0; 53 for(int i = head[t] ; i ; i = Ed[i].upEd) 54 if(Ed[i].f && dis[Ed[i].end] < dis[t] + Ed[i].c){ 55 dis[Ed[i].end] = dis[t] + Ed[i].c; 56 flo[Ed[i].end] = min(Ed[i].f , flo[t]); 57 pre[Ed[i].end] = i; 58 if(!vis[Ed[i].end]){ 59 vis[Ed[i].end] = 1; 60 q.push(Ed[i].end); 61 } 62 } 63 } 64 return dis[T] != dis[T + 1]; 65 } 66 67 int EK(){ 68 int ans = 0; 69 while(SPFA()){ 70 int cur = T , sum = 0; 71 while(cur != S){ 72 sum += Ed[pre[cur]].c; 73 Ed[pre[cur]].f -= flo[T]; 74 Ed[pre[cur] ^ 1].f += flo[T]; 75 cur = Ed[pre[cur] ^ 1].end; 76 } 77 ans += sum * flo[T]; 78 } 79 return ans; 80 } 81 82 void input(){ 83 a = read(); 84 b = read(); 85 N = read(); 86 M = read(); 87 T = id(N , M) + 1; 88 for(int i = 0 ; i <= N ; ++i) 89 for(int j = 0 ; j < M ; ++j){ 90 int k = read(); 91 addEd(id(i , j) , id(i , j + 1) , 1 , k); 92 addEd(id(i , j + 1) , id(i , j) , 0 , -k); 93 addEd(id(i , j) , id(i , j + 1) , INF); 94 addEd(id(i , j + 1) , id(i , j) , 0); 95 } 96 for(int j = 0 ; j <= M ; ++j) 97 for(int i = 0 ; i < N ; ++i){ 98 int k = read(); 99 addEd(id(i , j) , id(i + 1 , j) , 1 , k);100 addEd(id(i + 1 , j) , id(i , j) , 0 , -k);101 addEd(id(i , j) , id(i + 1 , j) , INF);102 addEd(id(i + 1 , j) , id(i , j) , 0);103 }104 for(int i = 1 ; i <= a ; ++i){105 int k = read() , p = read() , q = read();106 addEd(S , id(p , q) , k);107 addEd(id(p , q) , S , 0);108 }109 for(int i = 1 ; i <= b ; ++i){110 int k = read() , p = read() , q = read();111 addEd(id(p , q) , T , k);112 addEd(T , id(p , q) , 0);113 }114 }115 116 void work(){117 cout << EK();118 }119 120 int main(){121 #ifndef ONLINE_JUDGE122 freopen("in" , "r" , stdin);123 //freopen("out" , "w" , stdout);124 #endif125 input();126 work();127 return 0;128 }
给大家分享几个自己的脑残错误：
①第$N$个元素不一定在最长不下降子序列内
②题意杀……第二问中所有数字都只能取一次，第三问中同样的序列不能重复计算
但是相对来说还是很套路的
1 #include2 #define INF 0x3f3f3f3f 3 //This code is written by Itst 4 using namespace std; 5 6 inline int read(){ 7 int a = 0; 8 char c = getchar(); 9 bool f = 0; 10 while(!isdigit(c) && c != EOF){ 11 if(c == '-') 12 f = 1; 13 c = getchar(); 14 } 15 if(c == EOF) 16 exit(0); 17 while(isdigit(c)){ 18 a = (a << 3) + (a << 1) + (c ^ '0'); 19 c = getchar(); 20 } 21 return f ? -a : a; 22 } 23 24 const int MAXN = 5010 , MAXM = 50010; 25 struct Edge{ 26 int end , upEd , f , c; 27 }Ed[MAXM]; 28 int head[MAXN] , cur[MAXN] , dep[MAXN] , dp[MAXN] , num[MAXN]; 29 int N , S , T , cntEd = 1; 30 bool vis[MAXN]; 31 queue < int > q; 32 33 inline void addEd(int a , int b , int c , int d = 0){ 34 Ed[++cntEd].end = b; 35 Ed[cntEd].upEd = head[a]; 36 Ed[cntEd].f = c; 37 Ed[cntEd].c = d; 38 head[a] = cntEd; 39 } 40 41 inline bool bfs(){ 42 while(!q.empty()) 43 q.pop(); 44 q.push(S); 45 memset(dep , 0 , sizeof(dep)); 46 dep[S] = 1; 47 while(!q.empty()){ 48 int t = q.front(); 49 q.pop(); 50 for(int i = head[t] ; i ; i = Ed[i].upEd) 51 if(Ed[i].f && !dep[Ed[i].end]){ 52 dep[Ed[i].end] = dep[t] + 1; 53 if(Ed[i].end == T){ 54 memcpy(cur , head , sizeof(head)); 55 return 1; 56 } 57 q.push(Ed[i].end); 58 } 59 } 60 return 0; 61 } 62 63 inline int dfs(int x , int mF){ 64 if(x == T) 65 return mF; 66 int sum = 0; 67 for(int &i = cur[x] ; i ; i = Ed[i].upEd) 68 if(Ed[i].f && dep[Ed[i].end] == dep[x] + 1){ 69 int t = dfs(Ed[i].end , min(mF - sum , Ed[i].f)); 70 if(t){ 71 Ed[i].f -= t; 72 Ed[i ^ 1].f += t; 73 sum += t; 74 if(sum == mF) 75 break; 76 } 77 } 78 return sum; 79 } 80 81 int Dinic(){ 82 int ans = 0; 83 while(bfs()) 84 ans += dfs(S , INF); 85 return ans; 86 } 87 88 void input(){ 89 N = read(); 90 for(int i = 1 ; i <= N ; ++i) 91 num[i] = read(); 92 } 93 94 void work(){ 95 int maxN = 0 , ans = 0; 96 for(int i = 1 ; i <= N ; ++i){ 97 for(int j = i - 1 ; j >= 0 ; --j) 98 if(num[j] <= num[i]) 99 dp[i] = max(dp[i] , dp[j] + 1);100 maxN = max(maxN , dp[i]);101 }102 dp[N + 1] = maxN + 1;103 cout << maxN << endl;104 T = N * 2 + 1;105 for(int i = 1 ; i <= N ; ++i)106 if(dp[i] == 1){107 addEd(0 , i , 1);108 addEd(i , 0 , 0);109 }110 for(int i = 1 ; i <= N ; ++i){111 addEd(i , i + N , 1);112 addEd(i + N , i , 0);113 }114 for(int i = 1 ; i <= N ; ++i)115 for(int j = i + 1 ; j <= N ; ++j)116 if(dp[j] == dp[i] + 1 && num[j] >= num[i]){117 addEd(j , i + N , 0);118 addEd(i + N , j , 1);119 }120 for(int i = 1 ; i <= N ; ++i)121 if(dp[i] == maxN){122 addEd(i + N , T , 1);123 addEd(T , i + N , 0);124 }125 ans = Dinic();126 cout << ans << endl;127 if(maxN == 1)128 cout << ans;129 else{130 addEd(0 , 1 , INF);131 addEd(1 , 0 , 0);132 if(dp[N] == maxN){133 addEd(N * 2 , T , INF);134 addEd(T , N * 2 , 0);135 }136 addEd(1 , N + 1 , INF);137 addEd(N + 1 , 1 , 0);138 addEd(N , N * 2 , INF);139 addEd(N * 2 , N , 0);140 cout << ans + Dinic() << endl;141 }142 }143 144 int main(){145 #ifndef ONLINE_JUDGE146 freopen("in" , "r" , stdin);147 //freopen("out" , "w" , stdout);148 #endif149 input();150 work();151 return 0;152 }
费用流，没什么好说的
1 #include2 #define INF 0x7fffffff 3 using namespace std; 4 5 inline int read(){ 6 int a = 0; 7 char c = getchar(); 8 while(!isdigit(c)) 9 c = getchar(); 10 while(isdigit(c)){ 11 a = a * 10 + c - 48; 12 c = getchar(); 13 } 14 return a; 15 } 16 17 const int MAXN = 210; 18 struct Edge{ 19 int end , upEd , f , c; 20 }Ed[MAXN * MAXN * 5]; 21 int head[MAXN] , dis[MAXN] , pre[MAXN] , flo[MAXN] , b[MAXN] , c[MAXN] , cost[MAXN][MAXN]; 22 int cntEd = 1 , S , T , N , M , ans; 23 bool vis[MAXN]; 24 queue < int > q; 25 26 inline void addEd(int a , int b , int c , int d = 0){ 27 Ed[++cntEd].end = b; 28 Ed[cntEd].upEd = head[a]; 29 Ed[cntEd].f = c; 30 Ed[cntEd].c = d; 31 head[a] = cntEd; 32 } 33 34 bool SPFA(bool f){ 35 memset(dis , f ? -0x3f : 0x3f , sizeof(dis)); 36 dis[S] = 0; 37 q.push(S); 38 flo[S] = INF; 39 while(!q.empty()){ 40 int t = q.front(); 41 q.pop(); 42 vis[t] = 0; 43 for(int i = head[t] ; i ; i = Ed[i].upEd) 44 if(Ed[i].f && (f ? dis[Ed[i].end] < dis[t] + Ed[i].c : dis[Ed[i].end] > dis[t] + Ed[i].c)){ 45 dis[Ed[i].end] = dis[t] + Ed[i].c; 46 pre[Ed[i].end] = i; 47 flo[Ed[i].end] = min(flo[t] , Ed[i].f); 48 if(!vis[Ed[i].end]){ 49 vis[Ed[i].end] = 1; 50 q.push(Ed[i].end); 51 } 52 } 53 } 54 return dis[T] != dis[T + 1]; 55 } 56 57 signed main(){ 58 N = read(); 59 M = read(); 60 T = N + M + 1; 61 for(int i = 1 ; i <= N ; ++i) 62 b[i] = read(); 63 for(int j = 1 ; j <= M ; ++j) 64 c[j] = read(); 65 for(int i = 1 ; i <= N ; ++i) 66 for(int j = 1 ; j <= M ; ++j) 67 cost[i][j] = read(); 68 for(int i = 1 ; i <= N ; ++i){ 69 addEd(S , i , b[i]); 70 addEd(i , S , 0); 71 } 72 for(int i = 1 ; i <= M ; ++i){ 73 addEd(i + N , T , c[i]); 74 addEd(T , i + N , 0); 75 } 76 for(int i = 1 ; i <= N ; ++i) 77 for(int j = 1 ; j <= M ; ++j){ 78 addEd(i , j + N , INF , cost[i][j]); 79 addEd(j + N , i , 0 , -cost[i][j]); 80 } 81 ans = 0; 82 while(SPFA(0)){ 83 int cur = T , sum = 0; 84 while(cur != S){ 85 sum += Ed[pre[cur]].c; 86 Ed[pre[cur]].f -= flo[T]; 87 Ed[pre[cur] ^ 1].f += flo[T]; 88 cur = Ed[pre[cur] ^ 1].end; 89 } 90 ans += sum * flo[T]; 91 } 92 cout << ans << endl; 93 memset(head , 0 , sizeof(head)); 94 cntEd = 1; 95 for(int i = 1 ; i <= N ; ++i){ 96 addEd(S , i , b[i]); 97 addEd(i , S , 0); 98 } 99 for(int i = 1 ; i <= M ; ++i){100 addEd(i + N , T , c[i]);101 addEd(T , i + N , 0);102 }103 for(int i = 1 ; i <= N ; ++i)104 for(int j = 1 ; j <= M ; ++j){105 addEd(i , j + N , INF , cost[i][j]);106 addEd(j + N , i , 0 , -cost[i][j]);107 }108 ans = 0;109 while(SPFA(1)){110 int cur = T , sum = 0;111 while(cur != S){112 sum += Ed[pre[cur]].c;113 Ed[pre[cur]].f -= flo[T];114 Ed[pre[cur] ^ 1].f += flo[T];115 cur = Ed[pre[cur] ^ 1].end;116 }117 ans += sum * flo[T];118 }119 cout << ans << endl;120 return 0;121 }
分层图最短路
注意到终点时可以空油（在这里WA#4调了好久QAQ)
1 #include2 using namespace std; 3 4 inline int read(){ 5 int a = 0; 6 char c = getchar(); 7 while(!isdigit(c)) 8 c = getchar(); 9 while(isdigit(c)){10 a = a * 10 + c - 48;11 c = getchar();12 }13 return a;14 }15 16 const int dir[4][2] = { 0,1,1,0,-1,0,0,-1};17 int dis[110][110][11] , Map[110][110] , cost[4];18 int N , K , A , C; 19 struct que{20 int d , a , b , c;21 bool operator <(const que l)const{22 return d > l.d;23 }24 }now;25 priority_queue < que > q;26 27 #define AD now.a + dir[i][0]28 #define BD now.b + dir[i][1]29 int Dijk(){30 memset(dis , 0x7f , sizeof(dis));31 dis[1][1][0] = 0;32 q.push((que){ 0 , 1 , 1 , 0});33 while(!q.empty()){34 now = q.top();35 q.pop();36 if(now.d > dis[now.a][now.b][now.c])37 continue;38 if(now.a == N && now.b == N)39 return now.d;40 for(int i = 0 ; i < 4 ; ++i)41 if(AD > 0 && AD <= N)42 if(BD > 0 && BD <= N){43 int cnt = now.d + cost[i] , c = now.c + 1;44 if(c > K){45 cnt += C + A;46 c = 1;47 }48 if(Map[AD][BD]){49 cnt += A;50 c = 0;51 }52 if(dis[AD][BD][c] > cnt){53 dis[AD][BD][c] = cnt;54 q.push((que){dis[AD][BD][c] , AD , BD , c});55 }56 }57 }58 }59 60 signed main(){61 N = read();62 K = read();63 A = read();64 cost[2] = cost[3] = read();65 C = read();66 for(int i = 1 ; i <= N ; ++i)67 for(int j = 1 ; j <= N ; ++j)68 Map[i][j] = read();69 cout << Dijk();70 return 0;71 }
同餐巾计划问题，是一个有上下界网络流
每个图上的点拆成$AB$两个点，$S->B$，$A->T$，然后图上的有向边$x->y$在网络流中对应$B_x->A_y$
最大流之后每一条流满的$B_x->A_y$边表示边$x->y$被选中
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
按照题目给出的图片黑白染色，发现限制条件和点之间变成了一个二分图。
所以要求二分图最大独立集，同方格取数问题。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
费用流同深海机器人问题
输出方案直接在反边上暴搜
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
状压最短路
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
按照给的条件建图然后费用流即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
可以发现这是一个最小路径覆盖问题的翻版，限定总路径数求最大点数
每一次加入一个球，考虑是否存在$S$到$T$的流
对于每一个数$i$，拆成$A_i,B_i$，$S->B_i$流量为$1$，$A_i->T$流量为$1$，$B_i->T'$流量为$1$，$T'->T$流量为$K$，和为平方数的两个数$i,j(i>j)$之间建边$B_i->A_j$流量为$1$
在残量网络上若一条边$B_i->A_j$满流表示$i$在$j$上面，$T'$点用来限制柱子数量
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
与原题等价的题意是：从$1$到$N$找两条除起终点外不相交的路径使得经过的点数最多
拆点费用流即可
1 // luogu-judger-enable-o2 2 #include3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include
判断无解用并查集
第二问考虑二分
设$mid$为当前二分的答案，则将所有星球拆成$mid+1$个点表示每个星球在$0,1,2...mid$时刻的状态
如果使用Dinic，则枚举时间、每一次加点会更快
1 // luogu-judger-enable-o2 2 #include3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include
原题的等价题意：取$K$个区间集，每个区间只能在所有区间集中最多出现一次，且满足每个区间集内区间两两不交，求最长的区间集长度之和
建立费用流模型：数轴上每个整点$i$对应网络流中的点$i$：$i->i+1$，流量$K$费用$0$；对于区间$(l_i,r_i)$，$l_i -> r_i$，流量$1$费用$r_i - l_i$。
那么每一次增广都意味着在剩余没有被选中的区间中选择一些区间，成为一个新的区间集。
离散化、跑最大费用最大流即可
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include
同最长K可重区间集
值得注意的是有可能有线段$(x_1,y_1),(x_2,y_2)$满足$x_1=x_2$，所以对于每一个数轴上的整点$i$需要拆成两个点$A_i,B_i$，$A_i->B_i$表示覆盖点$i$
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include