RT , 在这道题中 , 如果使用优化建图的方法 , 需要建立虚点 . 但是我这么写 :

ffor(i,1,n) {
		map<int,vector<int>> mp;
		for(auto pr:val[i]) mp[pr.first].push_back(pr.second);
		for(auto it=mp.begin();it!=mp.end()&&it!=(--mp.end());++it) {
			vector<int> v1=it->second; auto It=++it; vector<int> v2=It->second;
			++idx;
			for(auto v:v1) G[idx].push_back(v),deg[v]++;
			for(auto v:v2) G[v].push_back(idx),deg[idx]++;
		}
	}

val 存的是每一行的所有非零的值 , 已经排过序 , 总会 Wa 很少的点 .

改成这样 :

ffor(i,1,n) {
		//map<int,vector<int>> mp;
		int lstid=0,lstv=0;
		for(auto pr:val[i]) {
			int v=pr.first,id=pr.second;	
			if(v!=lstv) {if(lstid) lstid=idx; else lstid=-1; ++idx,lstv=v;}
			G[idx].push_back(id),deg[id]++;
			if(lstid!=-1) G[id].push_back(lstid),deg[lstid]++;
		}
	}

却过了 . 二者唯一的区别大概是 , 每一行最大的几个点没有连上自己的虚点 , 但是这样应该不影响啊 , 因为数值最大的点对应的虚点在拓扑最开始就可以删掉了 . 难道是 STL 有什么魔幻的操作吗 ?