Error: value of 0000000abadfe087 too large for field of 4 bytes at 0000000000000
//出问题的文档：
soc-Epinions1.rar
(1.48 MB)
程序代码：#include<iostream>
#include<queue>
#include <algorithm>
#include <string.h>
#include <fstream>
using namespace std;
const long long int MAXN=75890;// 最大点数
const long long int Maxn=508840;//边数
const long long int INF=1<<28;// 距离初始值
long long int bmap[MAXN][MAXN];//二分图
long long int cx[MAXN];//cx[i]表示左集合i顶点所匹配的右集合的顶点序号
long long int cy[MAXN]; //cy[i]表示右集合i顶点所匹配的左集合的顶点序号
long long int G_1[Maxn],G_2[Maxn];
//三处文件名需要修改，一处最大点值需要修改
long long int nx,ny;
long long int dx[MAXN];
long long int dy[MAXN];
long long int dis;
bool bmask[MAXN];
//寻找 增广路径集
extern long long int getInputData(const char *fileName, long long int rowNum,long long int colNum, long long int *X, long long int *Y);
extern long long int getFileRows(const char *fileName);
extern long long int getFileColumns(const char * fileName);
bool searchpath()
{
queue<long long int>Q;
dis=INF;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(long long int i=1;i<=nx;i++)
{
//cx[i]表示左集合i顶点所匹配的右集合的顶点序号
if(cx[i]==-1)
{
//将未遍历的节点 入队 并初始化次节点距离为0
Q.push(i);
dx[i]=0;
}
}
//广度搜索增广路径
while(!Q.empty())
{
long long int u=Q.front();
Q.pop();
if(dx[u]>dis) break;
//取右侧节点
for(long long int v=1;v<=ny;v++)
{
//右侧节点的增广路径的距离
if(bmap[u][v]&&dy[v]==-1)
{
dy[v]=dx[u]+1; //v对应的距离 为u对应距离加1
if(cy[v]==-1) dis=dy[v];
else
{
dx[cy[v]]=dy[v]+1;
Q.push(cy[v]);
}
}
}
}
return dis!=INF;
}
//寻找路径 深度搜索
long long int findpath(long long int u)
{
for(long long int v=1;v<=ny;v++)
{
//如果该点没有被遍历过 并且距离为上一节点+1
if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1)
{
//对该点染色
bmask[v]=1;
if(cy[v]!=-1&&dy[v]==dis)
{
continue;
}
if(cy[v]==-1||findpath(cy[v]))
{
cy[v]=u;cx[u]=v;
return 1;
}
}
}
return 0;
}
//得到最大匹配的数目
long long int MaxMatch()
{
long long int res=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(searchpath())
{
memset(bmask,0,sizeof(bmask));
for(long long int i=1;i<=nx;i++)
{
if(cx[i]==-1)
{
res+=findpath(i);
}
}
}
return res;
}
int main()
{
long long int num,num1;
long long int r_num,c_num,success;
scanf("%d",&num);
num1=num;
// while(num--)
// {
memset(bmap,0,sizeof(bmap));
memset(G_1,0,sizeof(G_1));
memset(G_2,0,sizeof(G_2));
scanf("%d%d",&nx,&ny);
/*for(int i=1;i<=nx;i++)
{
int snum;
scanf("%d",&snum);
int u;
for(int j=1;j<=snum;j++)
{
scanf("%d",&u);
bmap[i][u]=1;
// bmap[u][i]=1;
}
} */
// cout<<MaxMatch()<<endl;
r_num=getFileRows("soc-Epinions1e.txt");
c_num=getFileColumns("soc-Epinions1.txt");
success=getInputData("soc-Epinions1.txt",r_num,c_num,G_2,G_1);
//cout<<r_num<<" "<<c_num<<" "<<G_1[1]<<" "<<G_2[1]<<endl;
for (long long int i=0;i<=r_num;i++)
{
bmap[G_1[i]][G_2[i]]=1;
}
if(MaxMatch()==nx)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
cout<<"最大匹配数是："<<MaxMatch()<<endl;
// cout<<"对应的匹配关系是："<<endl;
// for(int i=1;i<=nx;i++)
// {
// cout<<i<<" "<<cx[i]<<endl;
// }
cout<<"控制节点个数："<<num1-MaxMatch()<<endl;
// cout<<"!!!!!!!!!!!!!!"<<endl;
//for(int i=1;i<=ny;i++)
//{
// cout<<cy[i]<<" "<<i<<endl;
// }
// }
//system("pause");
return 0;
}
long long int getInputData(const char *fileName, long long int rowNum, long long int colNum, long long int *X, long long int *Y)
{
ifstream fileStream;
string oneLine = ""; //输入文件的某一行
double tmp = 0; //当前位置上的数值
long long int rowCount; // 行数计数器
long long int colCount =0; // 列数计数器
long long int index =0; // 当前位置在X[]数组的下标
long long int maxIndex = rowNum * (colNum -1) - 1;
// 打开文件
fileStream.open(fileName,ios::in); //ios::in 表示以只读的方式读取文件
if(fileStream.fail())//文件打开失败:返回0
{
cout << "文件不存在." << endl;
fileStream.close();
system("pause");
return 0;
}
else//文件存在
{
// 读入数据
rowCount =0; //初始化当前行数为0
colCount = 0; //当前列数清零
double tmp = 0; //当前读入的数值
while (!fileStream.eof()){
fileStream >> tmp;
if (colCount == 0){ //第一列，是标签Y
if (rowCount < rowNum){ //越界检查
Y[rowCount] = tmp;
//cout << Y[rowCount] << endl;
}
else{
cout << "计算出的行数与输入数据不符，请检查数据（如文件末尾不能有空行）." << endl;
fileStream.close();
system("pause");
return 0;
}
}
else{ //非第一列，是数据X
index = rowCount * (colNum -1) + colCount -1;
if (index <= maxIndex){ //越界检查
X[index] = tmp;
//cout << X[index] << endl;
}
else{
cout << "X[]下标超出数组范围，可能是文件中某行的列数>第一行的列数，退出！" << endl;
fileStream.close();
system("pause");
return 0;
}
}
if ('\n' != fileStream.peek()){ // 未到行尾，colCount累加，rowCount不变
++colCount;
}
else{ //已到行尾，colCount清零，rowCount累加
if ((colCount + 1) != colNum) //越界检查
{
cout << "第" << rowCount + 1 <<"行，输入的列数与文件列数不一致，请检查数据." << endl;
fileStream.close();
system("pause");
return 0;
}
else{
rowCount++; // 换下一行
colCount = 0; // 列数清零
}
}
}
// 关闭文件
fileStream.close();
return 1 ;
}
}// END OF getInputData
//文本的行数
long long int getFileRows(const char *fileName)
{
ifstream fileStream;
string tmp;
long long int count = 0;// 行数计数器
fileStream.open(fileName,ios::in);//ios::in 表示以只读的方式读取文件
if(fileStream.fail())//文件打开失败:返回0
{
return 0;
}
else//文件存在
{
while(getline(fileStream,tmp,'\n'))//读取一行
{
if (tmp.size() > 0 )
count++;
}
fileStream.close();
return count ;
}
}
//文本的列数
long long int getFileColumns(const char * fileName)
{
ifstream fileStream ;
// fileStream.open(fileName,std::ios::_Nocreate);
fileStream.open(fileName,ios::in);
double tmp = 0;
long long int count = 0; // 列数计数器
char c; //当前位置的字符
c = fileStream.peek();
while (('\n' != c) && (! fileStream.eof())) // 指针指向的当前字符，仅观测，不移动指针位置
{
fileStream >> tmp;
++count;
c = fileStream.peek();
}
fileStream.close();
return count;
}
