记录编号	93814	评测结果	AAAAAAAAAA
题目名称	[SGU U206]道路	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2014-03-28 16:44:19	内存使用	0.97 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=410,SIZEn=110,INF=0x7fffffff/2;
int n,m;
class EDGE{
public:
	int from,to,cost,id;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
int father[SIZEn]={0};
bool flag[SIZEn]={0};
int depth[SIZEn]={0};
int N;//二分图左右两端的点数
int cedge[SIZEN][SIZEN]={0};
int slack[SIZEN]={0};
bool visitx[SIZEN]={0},visity[SIZEN]={0};//右边的访问
int labelx[SIZEN]={0},labely[SIZEN]={0};
int match[SIZEN]={0};//右连左
bool findpath(int cx[SIZEN][SIZEN],int u){//左右都是1~N,左到右的邻接矩阵是cx
	visitx[u]=true;
	for(int i=1;i<=N;i++){
		if(visity[i]) continue;
		int t=labelx[u]+labely[i]-cx[u][i];
		if(t==0){//位于导出子图
			visity[i]=true;
			if(match[i]==-1||findpath(cx,match[i])){
				match[i]=u;
				return true;
			}
		}
		else slack[i]=min(slack[i],t);
	}
	return false;
}
int KM(int cx[SIZEN][SIZEN]){
	memset(match,-1,sizeof(match));
	memset(labely,0,sizeof(labely));
	for(int i=1;i<=N;i++){
		labelx[i]=INF;
		for(int j=1;j<=N;j++) labelx[i]=max(labelx[i],cx[i][j]);
	}
	for(int i=1;i<=N;i++){
		while(true){
			memset(visitx,0,sizeof(visitx)),memset(visity,0,sizeof(visity));
			for(int j=1;j<=N;j++) slack[j]=INF;
			if(findpath(cx,i)) break;
			int d=INF;
			for(int j=1;j<=N;j++) if(!visity[j]) d=min(d,slack[j]);
			for(int j=1;j<=N;j++) if(visitx[j]) labelx[j]-=d;
			for(int j=1;j<=N;j++) if(visity[j]) labely[j]+=d;
		}
	}
	int ans=0;
	for(int i=1;i<=N;i++) if(match[i]!=-1) ans+=cx[match[i]][i];
	return ans;
}
void work(void){
	int ans=KM(cedge);
	printf("%d\n",ans);
	//以下是输出方案的部分
	/*for(int i=1;i<=n-1;i++) printf("%d\n",edges[2*i-2].cost-labelx[i]);
	for(int i=n;i<=m;i++) printf("%d\n",edges[2*i-2].cost+labely[i]);*/
}
void addcedge(int v,int k){//x和其父亲边,第k条边
	EDGE &F=edges[father[v]];
	cedge[F.id][edges[k].id]=F.cost-edges[k].cost;
}
void makegraph(void){
	for(int i=2*(n-1);i<edges.size();i+=2){//正着和倒着只需要来一次
		int u=edges[i].from,v=edges[i].to;
		if(depth[u]>depth[v]) swap(u,v);//u在上v在下
		while(depth[v]>depth[u]) addcedge(v,i),v=edges[father[v]].from;
		while(u!=v) addcedge(v,i),addcedge(u,i),v=edges[father[v]].from,u=edges[father[u]].from;
	}
}
void DFS(int x,int f){
	flag[x]=true;
	father[x]=f;
	for(int i=0;i<c[x].size();i++){
		EDGE &now=edges[c[x][i]];
		if(now.id<=n-1&&!flag[now.to]){
			depth[now.to]=depth[x]+1;
			DFS(now.to,c[x][i]);
		}
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	int a,b,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&w);
		edges.push_back((EDGE){a,b,w,i});
		edges.push_back((EDGE){b,a,w,i});
		int tot=edges.size()-2;
		c[a].push_back(tot);
		c[b].push_back(tot+1);
	}
	N=m;
}
int main(){
	freopen("sgu206roads.in","r",stdin);
	freopen("sgu206roads.out","w",stdout);
	read();
	DFS(1,-1);
	makegraph();
	work();
	return 0;
}