线性代数丨《线性代数及其应用》思维导图
题目链接:https://vjudge.net/problem/POJ-1087
题目:有n个插座,插座上只有一个插孔,有m个用电器,每个用电器都有插头,它们的插头可以一样,
有k个插孔转化器, a b 的意思就是 可以把 b类的插孔变成a类的插孔,那么a类对于的插头就可以用这个插孔充电了。
问:没插孔的用电器最少有几个。
思路:源点->插座->用电器->汇点。
因为插座之间可以相互转化,可能A,B,C,D都可以变成E类的插座,所以插座之间的流应该为INF,其他的边流都是1,起到限流的作用。
编号比较麻烦,可以用map进行标记,编号。
这里N = 1100 ,之前写的代码N = 410,wa了 然后我N = 1100的过了之后,wa的代码直接复制提交到POJ居然过了。。。我是蒙蔽的,很无奈。
#include <iostream> #include <cstdio> #include <map> #include <string> #include <queue> #include <algorithm> #include <vector> using namespace std; const int N = 1100,INF = (int)1e9; int id,tot,s,t,all; int head[N],lev[N],cur[N]; map<string,int > mp; vector<string > ve[2]; queue<int > que; struct node{ int to,nxt,flow; }e[N*N]; inline void add(int u,int v,int flow){ e[tot].to = v; e[tot].flow = flow; e[tot].nxt = head[u]; head[u] = tot++; e[tot].to = u; e[tot].flow = 0; e[tot].nxt = head[v]; head[v] = tot++; } inline bool ID(char* name){ if(mp.count(name)) return true; else return false; } void build_map(){ for(int i = 0; i <= 1000; ++i) head[i] = -1; tot = 0; int n,m,k; char name1[30],name2[30]; scanf("%d",&n); for(int i = 1; i <= n; ++i){ scanf("%s",name1); if(!ID(name1)) mp[name1] = ++id; ve[0].push_back(name1); } //插座到用电器 scanf("%d",&m); all = m; for(int i = 1; i <= m; ++i){ scanf("%s%s",name1,name2); if(!ID(name1)) mp[name1] = ++id; if(!ID(name2)) mp[name2] = ++id; add(mp[name2],mp[name1],1); ve[1].push_back(name1); } //插座之间 scanf("%d",&k); for(int i = 1; i <= k; ++i){ scanf("%s%s",name1,name2); if(!ID(name1)) mp[name1] = ++id; if(!ID(name2)) mp[name2] = ++id; add(mp[name2],mp[name1],INF); } //原点到插座 s = 0, t = ++id; int num[2] = {ve[0].size(), ve[1].size()}; for(int i = 0; i < num[0]; ++i){ add(s,mp[ve[0][i]],1); } //用电器到汇点 for(int i = 0; i < num[1]; ++i){ add(mp[ve[1][i]],t,1); } } void show(){ cout << "id ====== " << id << endl; for(int i = 0; i <= id; ++i){ printf("当前点为 %d 相关联的点:",i); for(int o = head[i]; ~o; o = e[o].nxt){ printf("%d 流量为 %d ",e[o].to,e[o].flow); }cout << endl; } } bool bfs(int s,int t){ for(int i = s; i <= t; ++i) lev[i] = 0; while(!que.empty()) que.pop(); lev[s] = 1; que.push(s); while(!que.empty()){ int u = que.front(); que.pop(); for(int o = head[u]; ~o; o = e[o].nxt){ int v = e[o].to; if(!lev[v] && e[o].flow){ lev[v] = lev[u] + 1; if(v == t) return true; que.push(v); } } } return false; } int dfs(int now,int flow,int t){ if(now == t) return flow; int sum = 0,tmp; for(int o = cur[now]; ~o; o = e[o].nxt){ int to = e[o].to; if((lev[to] == lev[now] +1) && e[o].flow && (tmp = dfs(to,min(flow-sum,e[o].flow),t))){ e[o].flow -= tmp; e[o^1].flow += tmp; if((sum += tmp) == flow) return sum; } } return sum; } int mf(int s,int t){ int _mf = 0; while(bfs(s,t)){ for(int i = s; i <= t; ++i) cur[i] = head[i]; _mf += dfs(s,INF,t); } return _mf; } int main(){ build_map(); // show(); int _mf = mf(s,t); printf("%d\n",all -_mf); return 0; }
深入理解大数据之——事务及其ACID特性
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END