1419 最大团模板题

暴搜，可以加个简单的可行性剪枝
应该对n<50的图没什么鸭梨，poj上n有100估计数据比较水。

2677 双调平面旅行商问题

大意：一个旅行商必须不重复地从左侧的点走到右侧的点再走回到起点，求最短总路程。

O(n^2)
一般TSP是npc问题，这道题则可用dp。
把路径看成从起点走两条不同的路到最右侧点。
设dp[i][j]表示A到i，B到j的最短总路程，且A总是先于B，则存在两种转移：
\(dp[i][j]=dp[i-1][j]+dis(i,i-1)\) 表示A再走一步
\(dp[i][i-1]=min(dp[i][i-1],dp[i][j]+dis(i,j)) \)表示某个B点直连到i作为新的A点，原来的i-1作为B点。
显然由于平面上的距离原因A和B在中间不会经过同一个点，所以不用i==j的情况。
由三角关系知第n-1个点必须是第二个人走的，所以dp[n][n-1]补上最后一条边就是最终答案。