匈牙利算法DFS
bool dfs(int u){ for(int i = 1; i <= n; i++){ if(a[u][i] && !visit[i]){ visit[i] = true; if(match[i] == -1 || dfs(match[i])){ match[i] = u; } return true; } } return false; }
最优匹配KM算法
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #define LL long long #define eps 1e-8 #define INF 0x3f3f3f3f #define OPEN_FILE #define MAXM 1005 #define MAXN 205 using namespace std; int n, m; char s[MAXN][MAXM]; int a[MAXN][MAXN], match[MAXN], fx[MAXN], fy[MAXN]; bool x[MAXN], y[MAXN]; bool dfs(int u){ x[u] = true; for(int i = 1; i <= n; i++){ if(y[i]) continue; int p = fx[u] + fy[i] - a[u][i]; if(p == 0){ y[i] = true; if(match[i] == -1 || dfs(match[i])){ match[i] = u; return true; } }else{ m = min(m, p); } } return false; } void KM(){ int i,j; memset(fx,0,sizeof(fx)); memset(fy,0,sizeof(fy)); memset(match,-1,sizeof(match)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(a[i][j] > fx[i]){ fx[i] = a[i][j]; } } } for(int i = 1; i <= n; i++){ while(true){ memset(x, 0, sizeof(x)); memset(y, 0, sizeof(y)); m = INF; if(dfs(i)) break; for(int j = 1; j <= n; j++){ if(x[j]) fx[j] -= m; if(y[j]) fy[j] += m; } } } } int main() { #ifdef OPEN_FILE //freopen("inD.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // OPEN_FILE while(~scanf("%d", &n)){ memset(a, 0, sizeof(a)); for(int i = 1; i <= n; i++){ scanf("%s", s[i]); } for(int i = 1; i <= n; i++){ int p = strlen(s[i]); for(int j = 1; j <= n; j++){ if(i == j) continue; int q = strlen(s[j]) - 1; int cnt = 0; while(cnt < p && q >= 0 && s[i][cnt] == s[j][q]){ cnt++; q--; } a[i][j] = cnt; } } KM(); int ans = 0; for(int i = 1; i <= n; i++){ ans += a[match[i]][i]; } printf("%d ", ans); } }
2-SAT
这里面的add_clause的作用式是针对 x=xval or y=yval的时候加边,建不同的图要加不同的边,这里要注意下!!
比如还有一个经典的题目 HDU1824, 建图的时候要格外注意.对于前面队内关系来说是相互的,必须要有一个留下,但是对于队友关系来说却不是相互的,之存在A留B走而不存在A走B必须留的情况,所以加边的里面要写成单向的.
struct TwoSAT{ int n; vector<int> G[MAXN*2]; bool mark[MAXN*2]; int S[MAXN*2], c; bool dfs(int x){ if(mark[x^1]) return false; if(mark[x]) return true; mark[x] = true; S[c++] = x; for(int i = 0; i < G[x].size(); i++){ if(!dfs(G[x][i])) return false; } return true; } void init(int n){ this->n = n; for(int i = 0; i < n * 2; i++){ G[i].clear(); } memset(mark, 0, sizeof(mark)); } void add_clause(int x, int xval, int y, int yval){ x = x * 2 + xval; y = y * 2 + yval; G[x^1].push_back(y); G[y^1].push_back(x); } bool solve(){ for(int i = 0; i < n * 2; i += 2){ if(!mark[i] && !mark[i + 1]){ c = 0; if(!dfs(i)){ while(c > 0){ mark[S[--c]] = false; } if(!dfs(i + 1)){ return false; } } } } return true; } };
Max-Flow(Dinic)
struct Dinic{ int n, m, i, s, t; Edge e; vector<Edge> edges; vector<int> G[MAXN]; int d[MAXN], cur[MAXN]; bool vis[MAXN]; void init(int n){ this->n = n; for (i = 0; i <= n; i++){ G[i].clear(); } edges.clear(); } void AddEdge(int from, int to, int cap){ edges.push_back(Edge{ from, to, cap, 0 }); edges.push_back(Edge{ to, from, 0, 0 }); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS(){ memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()){ int x = Q.front(); Q.pop(); for (i = 0; i < G[x].size(); i++){ Edge& e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow){ vis[e.to] = true; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a){ if (x == t || a == 0) return a; int flow = 0, f; for (int& i = cur[x]; i < G[x].size(); i++){ Edge& e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0){ e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int MaxFlow(int s, int t, int need){ int flow = 0; this->s = s; this->t = t; while (BFS()){ memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); if (flow > need) return flow; } return flow; } bool checkFull(int s){ for (int i = 0; i < G[s].size(); i++){ if (edges[G[s][i]].flow != edges[G[s][i]].cap){ return false; } } return true; } };
MCMF
struct Edge{ int u,v,c,cost,next; }edge[E]; int head[V],cnt; void init(){ cnt=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int c,int cost) { edge[cnt].u=u;edge[cnt].v=v;edge[cnt].cost=cost; edge[cnt].c=c;edge[cnt].next=head[u];head[u]=cnt++; edge[cnt].u=v;edge[cnt].v=u;edge[cnt].cost=-cost; edge[cnt].c=0;edge[cnt].next=head[v];head[v]=cnt++; } bool spfa(int begin,int end){ int u,v; queue<int> q; for(int i=0;i<=end+2;i++){ pre[i]=-1; vis[i]=0; dist[i]=inf; } vis[begin]=1; dist[begin]=0; q.push(begin); while(!q.empty()){ u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ if(edge[i].c>0){ v=edge[i].v; if(dist[v]>dist[u]+edge[i].cost){ dist[v]=dist[u]+edge[i].cost; pre[v]=i; if(!vis[v]){ vis[v]=true; q.push(v); } } } } } return dist[end]!=inf; } int MCMF(int begin,int end){ int ans=0,flow; int flow_sum=0; while(spfa(begin,end)){ flow=inf; for(int i=pre[end];i!=-1;i=pre[edge[i].u]) if(edge[i].c<flow) flow=edge[i].c; for(int i=pre[end];i!=-1;i=pre[edge[i].u]){ edge[i].c-=flow; edge[i^1].c+=flow; } ans+=dist[end]; flow_sum += flow; } //cout << flow_sum << endl; return ans; }