本文共 2747 字，大约阅读时间需要 9 分钟。
题意:在一个会议室里有n种插座，每种插座一个；每个插座只能插一种以及一个电器（或者适配器）；
建图：
(1) 源点到每种插座连一条权值为1的边
(2) 每个电器到汇点连一条权值为1的边
(3) m个电器中，连一条对应插座到该个电器的边，权值为1
(4)k种适配器，连一条B到A的边，权值为inf
题目意思最多也就300个点，怎么开n=300，就re了，开600多，就AC了，求过路大神指点
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define inf 0x7fffffff 9 #define N 666 10 #define M 350000 11 map mp; 12 struct Edge 13 { 14 int v,w,next; 15 Edge(){} 16 Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){} 17 }edge[M]; 18 int pre[N],cur[N],dis[N],gap[N]; 19 int size,head[N]; 20 int a[105]; 21 void Init() 22 { 23 memset(head,-1,sizeof(head)); 24 size = 0; 25 } 26 void InsertEdge(int u,int v,int w)// 加边 27 { 28 edge[size] = Edge(v,w,head[u]); 29 head[u] = size++; 30 edge[size] = Edge(u,0,head[v]); 31 head[v] = size++; 32 } 33 int Isap(int st,int ed,int n) // Isap模板 34 { 35 for(int i=0; i<=n; i++) 36 { 37 gap[i] = dis[i] = 0; 38 cur[i] = head[i]; 39 } 40 int u = pre[st] = st; 41 int aug = inf ,maxflow = 0; 42 while(dis[st] < n) 43 { 44 loop: 45 for(int &i=cur[u]; i!=-1; i=edge[i].next) 46 { 47 int v = edge[i].v; 48 if(edge[i].w && dis[u]==dis[v]+1) 49 { 50 aug = min(aug,edge[i].w); 51 pre[v] = u; 52 u = v; 53 if(v==ed) 54 { 55 maxflow += aug; 56 for(u=pre[u]; v!=st; v=u,u=pre[u]) 57 { 58 edge[cur[u]].w -= aug; 59 edge[cur[u]^1].w += aug; 60 } 61 aug = inf; 62 } 63 goto loop; 64 } 65 } 66 int mindis = n; 67 for(int i=head[u]; i!=-1; i=edge[i].next) 68 { 69 int v = edge[i].v; 70 if(edge[i].w && dis[v] < mindis) 71 { 72 cur[u] = i; 73 mindis = dis[v]; 74 } 75 } 76 if(--gap[dis[u]]==0) break; 77 gap[dis[u]=mindis+1]++; 78 u = pre[u]; 79 } 80 return maxflow; 81 } 82 83 int main() 84 { 85 int T,n,m,k,st,ed,nv; 86 string s1,s2; 87 Init(); 88 mp.clear(); 89 scanf("%d",&n); 90 st = 0 ; nv = 1; //源点st为0，nv初始化为1，方便源点从0开始 91 for(int i=0; i >s1; 94 if(mp.find(s1)==mp.end()) mp[s1] = nv++; //map映射 95 InsertEdge(st,mp[s1],1); //源点到每种插座连一条权值为1的边 96 } 97 scanf("%d",&m); 98 int cnt=0; 99 for(int i=0; i >s1>>s2;102 if(mp.find(s1)==mp.end()) mp[s1] = nv++; //map映射 103 if(mp.find(s2)==mp.end()) mp[s2] = nv++; //map映射 104 InsertEdge(mp[s2],mp[s1],1); //m个电器中，连一条对应插座到该个电器的边，权值为1105 a[cnt++] = mp[s1]; //数组a记录设备的结点号 106 }107 scanf("%d",&k);108 for(int i=0; i >s1>>s2;111 if(mp.find(s1)==mp.end()) mp[s1] = nv++; //map映射 112 if(mp.find(s2)==mp.end()) mp[s2] = nv++; //map映射 113 InsertEdge(mp[s2],mp[s1],inf); //k种适配器，连一条B到A的边，权值为inf114 }115 ed = nv;// 汇点 116 for(int i=0; i
转载于:https://www.cnblogs.com/ar940507/p/3265554.html
