https://leetcode-cn.com/conte...这个题目之前写过状态压缩dp的解决方法。状态压缩dp先检查2^m个状态是否合法，然后每一行枚举这些合法状态中最好的解。时间复杂度很高。看到解决方案里面有网络流量解决方案。原方案是c++版的，我写的是python版的。原来的解题方法用的是Dinic算法，我用的是比较简单的Ford-Fulkerson算法。那么python在建图的时候会更加灵活。基本方法是：另外定义一个源点和一个汇点。在我的代码中每个点都有编号，源点固定为0，汇点固定为1。在第一个for循环中，每个可用的座位都会从图中的2开始编号。（cur变量初始化为2），然后从源点到所有偶数列连边。奇数列中的所有顶点都连接到汇点。（注意这条边是有向的）代码为每个点编号，建立边与汇点和源点edges=[[],[]]s=0t=1cur=2foriinrange(n):forj在范围(m):ifseats[i][j]=='.':edges.append([])ifj&1==1:#evenedges[s].append(cur)else:edges[cur].append(t)seats[i][j]=curcur+=1之前的数字：["#",".","#","#",".","#"]["“。“，“＃“，“＃“，“＃“，“＃“，“。“][“＃“，“。“，“＃“，“＃“，“。“，“＃“]后数字：['#',2,'#','#',3,'#'][4,'#','#','#','#',5]['#',6,'#','#',7,'#']编号完成，源点连接偶数列，奇数列连接汇点，这已经是二分图了图。图没有连接。然后我们把冲突的（也就是能看到别人答案的）座位两两连起来，但是这跟谁能抄谁没有关系，而是必须从偶数列连到奇数列。简化后的图是这样的求反向边虽然边是单向的，但算法中有两个操作：增加边上的流量（从前向边上的一点到另一点）减少边上的流量edge（从一点到另一点沿着反向边）所以求反向边的代码很简单，就是在edges中对边进行反向。edges2=[[]foriinrange(len(edges))]fors,einenumerate(edges):ifs==0:continueforiine:ifi==1:continueedges2[i].append(s)寻求dfs函数的最大流。每次都找一条增广路，直到找不到增广路为止。增广路径是从s（数字0）到t（数字1）的简单路径（简单路径是非循环的）。所以定义一个vis数组来标记是否到了某个点，防止循环出现。vis=[False]*len(edges)因为这里每条边的流都是1。所以我们只定义一个二维矩阵，可以表示任意两点之间是否有流。flag=[[False]*len(edges)for_inedges]flagi为True，表示从i到j有流（当然需要存在边）。如果有流动，它不能前进，但它可以倒退。没有流量时情况正好相反。最后答案是可用的座位数-最大流量代码classSolution:defmaxStudents(self,seats:List[List[str]])->int:n=len(seats)m=len(seats[0])edges=[[],[]]s=0t=1cur=2foriinrange(n):forjinrange(m):ifseats[i][j]=='.':edges.append([])ifj&1==1:#偶数edges[s].append(cur)else:edges[cur].append(t)seats[i][j]=curcur+=1ifcur==2:返回0foriinrange(n):forjinrange(m):ifseats[i][j]!='#':cur=seats[i][j]ifj+1
